ریاضیدانان تلاش خود را برای ساخت مکعب های کروی کامل کردند

در قرن چهارم، ریاضیدان یونانی پاپوس اسکندریه، زنبورهای عسل را به دلیل «تفکر هندسی» آنها تحسین کرد. ساختار شش ضلعی لانه زنبوری آنها راه بهینه ای برای تقسیم فضای دو بعدی به سلول هایی با مساحت مساوی و حداقل محیط به نظر می رسید - به حشرات اجازه می داد میزان تولید موم را کاهش دهند و زمان و انرژی کمتری را صرف ساختن خود کنند. کندو

یا اینطور فرضیه پاپوس و دیگران بود. برای هزاران سال، هیچ کس نمی توانست ثابت کند که شش ضلعی ها بهینه هستند - تا اینکه سرانجام، در سال 1999، ریاضیدان توماس هیلز نشان داد که هیچ شکل دیگری نمی تواند بهتر عمل کند. امروزه ریاضیدانان هنوز نمی دانند که کدام اشکال می توانند سه بعدی یا بیشتر را با کمترین سطح ممکن کاشی کنند.

مشخص شده است که این مسئله "فوم" کاربردهای گسترده ای دارد - برای فیزیکدانانی که رفتار حباب های صابون (یا فوم ها) را مطالعه می کنند و شیمیدانانی که ساختار کریستال ها را تجزیه و تحلیل می کنند، برای ریاضیدانانی که ترتیبات بسته بندی کره را بررسی می کنند و آماردانانی که تکنیک های پردازش داده موثر را توسعه می دهند. .

در اواسط دهه 2000، فرمول خاصی از مسئله فوم نیز توجه دانشمندان نظری کامپیوتر را به خود جلب کرد، آنها در کمال تعجب متوجه شدند که این مشکل عمیقاً به یک مشکل باز مهم در حوزه آنها مرتبط است. آنها توانستند از این اتصال برای یافتن یک شکل جدید با ابعاد بالا با حداقل مساحت سطح استفاده کنند.

گفت: "من عاشق این رفت و برگشت هستم." عساف نور از دانشگاه پرینستون برخی از ریاضیات قدیمی به علوم کامپیوتر مرتبط می شوند. علوم کامپیوتر جواب می دهد و سوال را در ریاضیات حل می کند. وقتی این اتفاق می افتد خیلی خوب است.»

اما این شکل، اگرچه بهینه بود، اما چیزی مهم را از دست داد: یک پایه هندسی. از آنجایی که وجود آن با استفاده از تکنیک های علوم کامپیوتر ثابت شده بود، درک هندسه واقعی آن دشوار بود. این چیزی است که Naor، همراه با آن اودد رگو، یک دانشمند کامپیوتر در موسسه کورانت در دانشگاه نیویورک، تصمیم گرفت تا آن را اصلاح کند مدرکی که ماه گذشته به صورت آنلاین منتشر شد.

رگو گفت: «این پایان بسیار خوبی برای داستان است.

فوم های مکعبی

ریاضیدانان نسخه‌های دیگری از مشکل فوم را در نظر گرفته‌اند - از جمله اینکه چه اتفاقی می‌افتد اگر فقط اجازه داشته باشید فضا را بر اساس آنچه شبکه عدد صحیح نامیده می‌شود تقسیم کنید. در آن نسخه از مسئله، شما یک آرایه مربعی از نقاط با فاصله مساوی (هر یک 1 واحد از هم) را می گیرید و هر یک از آن نقاط را مرکز یک شکل می کنید. مشکل فوم "مکعبی" این سوال را مطرح می کند که حداقل مساحت سطح زمانی که شما نیاز به کاشی کاری فضا به این روش دارید چقدر خواهد بود.

محققان در ابتدا علاقه مند به اعمال این محدودیت به منظور درک ویژگی های فضاهای توپولوژیکی به نام منیفولد بودند. اما این سوال زندگی خود را به خود گرفت و در تجزیه و تحلیل داده ها و سایر کاربردها مرتبط شد.

از نظر هندسی نیز جالب است، زیرا معنای «بهینه» را تغییر می‌دهد. به عنوان مثال، در دو بعد، شش ضلعی های منظم دیگر نمی توانند صفحه را کاشی کنند، اگر فقط با مقادیر صحیح در جهت افقی و عمودی جابجا شوند. (شما باید آنها را با مقادیر غیرمنطقی در یکی از دو جهت حرکت دهید.)

مربع ها می توانند. اما آیا این بهترین کاری است که می توان انجام داد؟ به عنوان ریاضیدان جایگیونگ چو در سال 1989 کشف شد، پاسخ منفی است. شکل مطلوب در عوض یک شش ضلعی است که در یک جهت له شده و در جهت دیگر کشیده شده است. (محیط چنین شش ضلعی تقریباً 3.86 است وقتی مساحت آن 1 باشد - از محیط مربع 4 غلبه می کند.)

این تفاوت ها ممکن است بی اهمیت به نظر برسند، اما در ابعاد بالاتر بسیار بزرگتر می شوند.

در میان تمام اشکال یک حجم معین، شکلی که سطح را به حداقل می رساند کره است. مانند n، تعداد ابعاد، رشد می کند، مساحت کره به نسبت ریشه دوم افزایش می یابد n.

اما کره ها نمی توانند فضا را بدون ایجاد شکاف کاشی کنند. از سوی دیگر، یک n-مکعب بعدی قوطی حجم 1. نکته این است که سطح آن 2 استn، متناسب با ابعاد آن رشد می کند. یک مکعب 10,000 بعدی با حجم 1 دارای مساحت 20,000 است - بسیار بزرگتر از 400، یعنی مساحت تقریبی یک کره 10,000 بعدی.

و بنابراین محققان تعجب کردند که آیا می توانند یک "مکعب کروی" پیدا کنند - شکلی که کاشی می شود nفضای بعدی، مانند یک مکعب، اما سطح آن به آرامی رشد می کند، مانند یک کره.

بعید به نظر می رسید. گفت: "اگر می خواهید حباب شما دقیقاً فضا را پر کند و روی این شبکه مکعبی متمرکز شود، فکر کردن به اینکه از چه چیزی بجز حباب مکعبی استفاده می کنید سخت است." رایان اودانل، دانشمند نظری کامپیوتر در دانشگاه کارنگی ملون. "واقعاً به نظر می رسد که مکعب باید بهترین باشد."

اکنون می دانیم که اینطور نیست.

سختی مسائل سخت

برای چندین دهه، مشکل فوم مکعبی در ابعاد بالاتر نسبتا ناشناخته ماند. اولین محققینی که در این زمینه پیشرفت کردند نه از قلمرو هندسه بلکه از علم کامپیوتر نظری بودند. آنها به طور تصادفی با آن برخورد کردند، در حالی که در جستجوی راهی برای اثبات یک بیانیه مرکزی در حوزه خود به نام the بودند حدس بازی های منحصر به فرد. رجف گفت: «حدس بازی‌های منحصربه‌فرد همان چیزی است که من در حال حاضر به‌عنوان بزرگ‌ترین سؤال باز در علم کامپیوتر نظری می‌دانم».

پیشنهاد در سال 2002 توسط ساب هاش خط، یک دانشجوی فارغ التحصیل در آن زمان، این حدس بیان می کند که اگر یک مشکل خاص - مشکلی که شامل تخصیص رنگ به گره های یک شبکه است - نمی تواند دقیقاً حل شود، پس پیدا کردن یک راه حل تقریبی نیز بسیار دشوار است. اگر این حدس درست باشد، به محققان این امکان را می دهد که پیچیدگی مجموعه وسیعی از وظایف محاسباتی دیگر را در یک لحظه درک کنند.

دانشمندان کامپیوتر اغلب وظایف را بر اساس اینکه آیا می توان آنها را با یک الگوریتم کارآمد حل کرد یا در عوض "NP-hard" هستند طبقه بندی می کنند (به این معنی که با بزرگتر شدن اندازه مشکل نمی توان آنها را به طور کارآمد حل کرد، تا زمانی که باور عمومی وجود داشته باشد. اما حدس اثبات نشده در مورد پیچیدگی محاسباتی درست است). به عنوان مثال، مشکل فروشنده دوره گرد، که کوتاه ترین مسیر مورد نیاز برای بازدید از هر شهر در یک شبکه را فقط یک بار می خواهد، NP-hard است. همچنین تعیین اینکه آیا یک نمودار - مجموعه ای از رئوس که توسط یال ها به هم متصل شده اند - می تواند با حداکثر سه رنگ برچسب گذاری شود، به طوری که هر دو راس متصل رنگ های متفاوتی داشته باشند یا خیر.

به نظر می رسد که یافتن راه حلی تقریبی برای بسیاری از این کارها بسیار سخت است. فرض کنید می خواهید رئوس یک نمودار را با رنگ های مختلف به گونه ای برچسب گذاری کنید که برخی از محدودیت ها را برآورده کند. اگر برآوردن تمام این محدودیت‌ها NP-سخت است، در مورد تلاش برای برآورده کردن فقط 90٪ یا 75٪ یا 50٪ آنها چطور؟ در زیر مقداری آستانه، ممکن است بتوان یک الگوریتم کارآمد ارائه کرد، اما بالاتر از آن آستانه، مشکل NP-hard می شود.

برای چندین دهه، دانشمندان کامپیوتر تلاش کرده‌اند تا آستانه‌هایی را برای مسائل مختلف بهینه‌سازی مورد علاقه تعیین کنند. اما برخی سوالات از این نوع توصیف طفره می روند. در حالی که یک الگوریتم ممکن است 80% بهترین راه حل را تضمین کند، ممکن است رسیدن به 95% بهترین راه حل NP-سخت باشد، و این سوال را که دقیقاً بین 80% تا 95% مشکل به قلمرو NP-hard منتهی می‌شود، حل نشده باقی می‌ماند.

حدس بازی‌های منحصربه‌فرد یا UGC راهی برای مشخص کردن فوری پاسخ ارائه می‌دهد. این بیانیه ای را بیان می کند که در ابتدا محدودتر به نظر می رسد: تشخیص تفاوت بین نموداری که می توانید تقریباً تمام مجموعه خاصی از محدودیت های رنگ آمیزی را برای آن برآورده کنید (مثلاً بیش از 99٪) و نموداری برای آن دشوار است. که به سختی می توانید هیچ کدام را برآورده کنید (مثلاً کمتر از 1٪).

اما مدت کوتاهی پس از ارائه UGC در سال 2002، محققان نشان دادند که اگر حدس درست باشد، می‌توانید آستانه سختی را برای هر مشکل رضایت محدودیت به راحتی محاسبه کنید. (این به این دلیل است که UGC همچنین نشان می‌دهد که یک الگوریتم شناخته‌شده بهترین تقریب ممکن را برای همه این مسائل به دست می‌آورد.) اودانل گفت: «این دقیقاً پایه اصلی همه این مسائل بهینه‌سازی بود.

و به این ترتیب دانشمندان نظری کامپیوتر شروع به اثبات UGC کردند - وظیفه ای که در نهایت باعث شد برخی از آنها مکعب های کروی را کشف کنند.

سخت کردن مشکلات سخت

در سال 2005، اودانل در Microsoft Research کار می کرد. او و دو همکار - اوریل فایگه، اکنون در موسسه علوم وایزمن، و گای کیندلر، اکنون در دانشگاه عبری اورشلیم - برای مقابله با UGC متحد شدند.

آنها تصور مبهمی از اینکه چگونه می خواهند ادامه دهند داشتند. آنها با یک سوال در مورد نمودارها شروع می کنند - سوالی که بسیار شبیه به UGC است. مسئله موسوم به حداکثر برش ("max-cut") وقتی به یک نمودار داده می شود، می پرسد که چگونه رئوس آن را به دو مجموعه (یا رنگ) تقسیم کنیم تا تعداد یال هایی که آن مجموعه ها را به هم متصل می کنند تا حد امکان زیاد باشد. (شما می توانید حداکثر برش را به عنوان سؤالی در مورد بهترین راه برای رنگ آمیزی نمودار با دو رنگ در نظر بگیرید، به طوری که تا حد ممکن کمترین لبه رئوس هم رنگ را به هم متصل کند.)

اگر UGC درست باشد، به این معنی است که، با توجه به برخی نمودارهای تصادفی، یک الگوریتم تقریب کارآمد تنها می تواند در حدود 87 درصد از برش حداکثر واقعی آن نمودار باشد. انجام هر کاری بهتر NP-سخت خواهد بود.

فایگی، کیندلر و اودانل در عوض می‌خواستند در جهت مخالف حرکت کنند: آنها امیدوار بودند نشان دهند که حداکثر برش تقریبی سخت است و سپس از آن برای اثبات UGC استفاده کنند. طرح آنها بر قدرت تکنیکی به نام تکرار موازی متکی بود - یک استراتژی هوشمندانه که مشکلات سخت را سخت‌تر می‌کند.

بگویید که می‌دانید تشخیص بین مشکلی که می‌توانید حل کنید و مشکلی که اکثراً می‌توانید حل کنید، سخت است. تکرار موازی شما را قادر می‌سازد که بر روی آن کار کنید تا نتیجه سختی بسیار قوی‌تری را نشان دهید: همچنین تشخیص NP-سخت بین مشکلی که می‌توانید حل کنید و مشکلی که به سختی می‌توانید حل کنید، دشوار است. ناور گفت: «این پدیده غیر شهودی و عمیق ... امروزه در بسیاری از علوم رایانه جای دارد.

اما یک گرفتاری وجود دارد. تکرار موازی همیشه سختی یک مشکل را آنقدر که دانشمندان کامپیوتر می خواهند تقویت نمی کند. به‌طور خاص، جنبه‌هایی از مشکل حداکثر برش وجود دارد که «سردرد بزرگی برای تکرار موازی ایجاد می‌کند».

فایگی، کیندلر و اودانل روی نشان دادن این نکته تمرکز کردند که تکرار موازی علیرغم سردردها می تواند کارساز باشد. گفت: "این یک چیز واقعاً پیچیده برای تجزیه و تحلیل است." دانا مشکویتز، دانشمند نظری کامپیوتر در دانشگاه تگزاس، آستین. «اما این به طرز وسوسه انگیزی نزدیک به نظر می رسید. تکرار موازی به نظر می‌رسید که به ایجاد این ارتباط از حداکثر برش به بازی‌های منحصربه‌فرد کمک می‌کند.»

به عنوان یک گرم کردن، محققان سعی کردند تکرار موازی را برای یک مورد ساده از حداکثر برش، چیزی که موشکویتز "احمقانه ترین برش حداکثر" نامید، درک کنند. تعداد فرد رئوس را در نظر بگیرید که توسط یال ها به هم متصل شده اند تا یک دایره یا "چرخه فرد" را تشکیل دهند. شما می خواهید هر راس را با یکی از دو رنگ برچسب گذاری کنید تا هیچ جفت رئوس مجاور هم رنگ نباشد. در این مورد، این غیرممکن است: یک لبه همیشه رئوس همرنگ را به هم متصل می کند. شما باید آن لبه را حذف کنید، چرخه فرد را "شکستن" کنید تا نمودار خود را برای ارضای محدودیت مشکل بدست آورید. در نهایت، شما می‌خواهید کل کسری از یال‌هایی را که باید حذف کنید تا به درستی نمودار خود را رنگ کنید، به حداقل برسانید.

تکرار موازی به شما این امکان را می دهد که نسخه ای با ابعاد بالا از این مشکل را در نظر بگیرید - نسخه ای که در آن باید تمام چرخه های عجیب و غریب را که ظاهر می شوند، بشکنید. Feige، Kindler و O'Donnell باید نشان دهند که با افزایش تعداد ابعاد، باید بخش بسیار زیادی از لبه‌ها را حذف کنید تا تمام چرخه‌های فرد را بشکنید. اگر این درست بود، به این معنی بود که تکرار موازی می‌تواند به طور موثری سختی این مشکل «حداکثر برش احمقانه» را تقویت کند.

در آن زمان بود که تیم یک تصادف عجیب را کشف کرد: یک روش هندسی برای تفسیر اینکه آیا تکرار موازی به روشی که آنها امیدوار بودند کار می کند وجود داشت. راز در سطح فوم های مکعبی نهفته است.

از لیمو تا لیموناد

مشکل آن‌ها که به زبان فوم‌ها بازنویسی شده بود، به این نتیجه رسید که نشان دهند مکعب‌های کروی نمی‌توانند وجود داشته باشند - اینکه تقسیم فضای با ابعاد بالا در امتداد شبکه عدد صحیح به سلول‌هایی با سطح بسیار کوچک‌تر از مکعب غیرممکن است. (همانطور که دانشمندان کامپیوتر امیدوار بودند نشان دهند یک سطح بزرگتر مربوط به نیاز به حذف لبه های "بد" بیشتر در نمودار چرخه های فرد است.)

اوه، چه مشکل هندسی عجیبی داشتیم، اما این احتمالاً درست است، درست است؟ اودانل گفت. ما واقعاً به آن نیاز داشتیم تا پاسخ واقعی باشد.» اما او، فیگی و کیندلر نتوانستند آن را ثابت کنند. بنابراین در سال 2007، آنها چاپ مقاله به تشریح نحوه برنامه ریزی آنها برای استفاده از این مشکل برای کمک به حمله به UGC.

به زودی امیدهایشان بر باد رفت.

ران راز، یک دانشمند نظری کامپیوتر در پرینستون که قبلا چندین نتیجه اصلی را در مورد تکرار موازی ثابت کرده بود، مجذوب مقاله آنها شد. او تصمیم گرفت تکرار موازی را برای مسئله چرخه فرد تحلیل کند، تا حدی به دلیل ارتباط با هندسه که فایگی، کیندلر و اودانل کشف کرده بودند.

راز با مشکل فوم شروع نکرد، بلکه به نسخه علوم کامپیوتری سوال حمله کرد. او نشان داد که می‌توانید با حذف لبه‌های بسیار کمتری برای شکستن تمام چرخه‌های عجیب و غریب در یک نمودار خلاص شوید. به عبارت دیگر، تکرار موازی نمی تواند به اندازه کافی سختی این مشکل برش حداکثر را تقویت کند. موشکویتز گفت: «پارامترهایی که فرد دقیقاً از تکرار موازی به دست می‌آورد، دقیقاً نمی‌تواند این را نشان دهد.

اودانل گفت: «برنامه ما برای استفاده از تکرار موازی برای نشان دادن سختی بازی‌های منحصربه‌فرد حتی در ساده‌ترین حالت هم جواب نداد. "این نوع کل نقشه را شکست."

اگرچه ناامیدکننده بود، اما نتیجه راز به وجود مکعب‌های کروی نیز اشاره کرد: اشکالی که قادر به کاشی‌کاری هستند. n-فضای بعدی با سطحی که متناسب با ریشه مربع مقیاس شده است n. اودانل گفت: «ما می‌خواستیم از لیمو لیموناد درست کنیم و این نتیجه فنی ناامیدکننده را در مورد تکرار موازی و نمودارهای مجزا بگیریم و آن را به یک نتیجه زیبا و جالب در هندسه تبدیل کنیم.

او و کیندلر با همکاری دانشمندان کامپیوتر آنوپ رائو و آوی ویگدرسون، بر روی اثبات Raz تمرکز کردند تا زمانی که تکنیک های آن را به خوبی یاد گرفتند تا آنها را به مشکل فوم ترجمه کنند. آنها در سال 2008 این را نشان دادند مکعب های کروی در واقع ممکن است.

گفت: "این یک راه خوب برای استدلال در مورد مشکل است." مارک براورمن پرینستون "زیباست."

و سوالاتی را در زمینه هندسه داستان ایجاد کرد. از آنجا که آنها از کار راز در مورد تکرار موازی برای ساختن شکل کاشی کاری خود استفاده کرده بودند، کیندلر، اودانل، رائو و ویگدرسون به چیزی زشت و فرانکشتاین مانند رسیدند. کاشی کثیف و پر از تورفتگی بود. از نظر ریاضی محدب نبود. در حالی که این برای اهداف آنها کار می کرد، مکعب کروی فاقد خواصی بود که ریاضیدانان ترجیح می دهند - ویژگی هایی که شکل را ملموس تر، تعریف و مطالعه آسان تر و برای کاربردهای بالقوه مناسب تر می کند.

رگو گفت: «یک چیز بسیار ناخوشایند در ساخت آنها وجود دارد. "به نظر می رسد یک آمیب است. شبیه آن چیزی نیست که شما انتظار دارید، یک بدنه کاشی کاری زیبا.”

این چیزی است که او و نائور به دنبال یافتن آن بودند.

آزاد شدن از قفس

از همان ابتدا، ناور و رگو متوجه شدند که باید از صفر شروع کنند. گفت: "تا حدی به این دلیل که اجسام محدب بسیار محدود کننده هستند، هیچ یک از تکنیک های قبلی هیچ شانسی برای کار نداشتند." دور مینزر، دانشمند نظری کامپیوتر در موسسه فناوری ماساچوست.

در واقع، کاملاً قابل قبول بود که تحدب بسیار محدود کننده باشد - که یک مکعب کروی محدب به سادگی وجود ندارد.

اما ماه گذشته، Naor و Regev ثابت کردند که می توانید پارتیشن بندی کنید n- فضای بعدی در امتداد عدد صحیح با یک شکل محدب که مساحت سطح آن بسیار نزدیک به کره است، هماهنگ می شود. و آنها این کار را کاملاً هندسی انجام دادند - مسئله را به ریشه های ریاضی آن برگرداندند.

آنها ابتدا باید از یک مانع بزرگ عبور می کردند. مشکل فوم مکعبی مستلزم آن است که هر کاشی در مرکز مختصات اعداد صحیح باشد. اما در شبکه اعداد صحیح، فواصل بسیار کوتاهی بین برخی نقاط وجود دارد - و این فواصل کوتاه باعث ایجاد مشکل می شود.

یک نقطه از شبکه دو بعدی را در نظر بگیرید. در جهات افقی و عمودی 1 واحد دورتر از نزدیکترین نقاط خود قرار دارد. اما در جهت مورب، نزدیک‌ترین نقطه $latex sqrt{2}$ واحد دورتر است - اختلافی که در فضاهای بزرگ‌تر بدتر می‌شود. در n-بعدی شبکه عدد صحیح، نزدیکترین نقاط هنوز 1 واحد فاصله دارند، اما آن نقاط "مورب" اکنون $latex sqrt{n}$ واحد فاصله دارند. مثلاً در 10,000 بعد، این بدان معنی است که نزدیکترین همسایه "مورب" به هر نقطه، 100 واحد دورتر است، حتی اگر 10,000،1 نقطه دیگر (یکی در هر جهت) وجود داشته باشد که تنها XNUMX واحد با هم فاصله دارند.

در شبکه های دیگر، این دو نوع فاصله متناسب با یکدیگر رشد می کنند. ریاضیدانان دهه هاست که می دانند چگونه چنین مشبک هایی را با اشکال محدب با حداقل سطح کاشی کاری کنند.

اما در شبکه اعداد صحیح، کوتاه‌ترین فاصله‌ها همیشه در 1 باقی می‌مانند. این امر مانع ایجاد یک کاشی زیبا با سطح بهینه می‌شود. رگو گفت: «آنها تو را به نوعی در این قفس گذاشتند. "آنها همه چیز را در اطراف شما بسیار تنگ می کنند."

بنابراین Naor و Regev در عوض یک برش از کامل را در نظر گرفتند n-فضای بعدی آنها با دقت این زیرفضا را انتخاب کردند تا همچنان از نظر نقاط صحیح غنی باشد، اما هیچ یک از آن نقاط خیلی به هم نزدیک نشوند.

به عبارت دیگر، فضای فرعی که آنها در نهایت به آن دست یافتند، دقیقاً از نوعی بود که ریاضیدانان قبلاً می‌دانستند چگونه به‌طور بهینه کاشی کاری کنند.

اما این فقط نیمی از کار بود. Naor و Regev نیاز داشتند که کل فضا را تقسیم کنند، نه فقط یک برش از آن. برای به دست آوردن یک n- مکعب کروی شکل، آنها باید کاشی کارآمد خود را با کاشی از فضای باقی مانده ضرب می کردند (مثل اینکه چگونه می توانید یک مربع دو بعدی را با یک قطعه خط یک بعدی ضرب کنید تا یک مکعب سه بعدی بدست آورید). انجام این کار ساخت آنها را به فضای اصلی باز می گرداند، اما سطح آن را نیز افزایش می دهد.

این جفت باید نشان می‌داد که کاشی از فضای باقی‌مانده، که بهینه نبود، مقدار زیادی به مساحت سطح اضافه نمی‌کرد. هنگامی که آنها این کار را انجام دادند، ساخت آنها کامل شد. (مساحت سطح شکل نهایی آنها کمی بزرگتر از مکعب کروی غیر محدب بود، اما آنها معتقدند که ممکن است کاشی محدب را پیدا کنیم که به اندازه همتای غیر محدب آن کارآمد باشد.)

این ریاضیدان گفت: "اثبات آنها کاملاً متفاوت است" با کار قبلی روی مکعب های کروی نوگا آلون. و در نگاهی به گذشته، شاید یک دلیل طبیعی تر باشد. این همان چیزی است که شاید کسی باید سعی می کرد با آن شروع کند.»

راز افزود: «وقتی کارها به گونه ای متفاوت انجام می شود، گاهی اوقات پیامدهای جالب دیگری پیدا می کنید.»

امید دوباره روشن شد

هنوز مشخص نیست که این پیامدها چه می‌تواند باشد - اگرچه کار به استفاده بالقوه از شبکه‌های عدد صحیح در رمزنگاری و سایر برنامه‌ها می‌پردازد. آلون گفت: با توجه به ارتباط این مشکل با زمینه های دیگر، «احتمالاً به چیزهای دیگری منتهی می شود».

در حال حاضر، دانشمندان کامپیوتر راهی برای تفسیر نتیجه محدب به زبان تکرار موازی و UGC نمی بینند. اما آنها به طور کامل از طرح اولیه برای استفاده از مشکل فوم برای اثبات حدس استفاده نکردند. کیندلر گفت: «راه‌های مختلفی وجود دارد که می‌توانید سعی کنید موانع آشکاری را که با آن‌ها مواجه شده‌ایم، از بین ببرید.

وقتی براورمن و مینزر این راه را امتحان کردند فوم‌های بازبینی شده در سال 2020. به‌جای اینکه شکل کاشی‌کاری محدب باشد، از آن خواستند که از تقارن‌های خاصی تبعیت کند، به طوری که بدون توجه به اینکه مختصات آن را چگونه برگردانید، یکسان به نظر برسد. (در دوبعدی، یک مربع کار می‌کند، اما یک مستطیل کار نمی‌کند؛ و نه مکعب‌های کروی با ابعاد بالا که تا به امروز توضیح داده شده است.) تحت این محدودیت جدید، این جفت توانست آنچه را که کیندلر و دیگران 2 سال قبل امیدوار بودند نشان دهند: که به هر حال شما نمی توانید خیلی بهتر از سطح مکعب انجام دهید.

این با نوع دیگری از تکرار موازی مطابقت داشت - تکراری که ساده‌ترین حالت برش حداکثر را به همان اندازه که لازم بود سخت می‌کرد. در حالی که نتیجه به این خط از تحقیقات امیدوار است، اما مشخص نیست که آیا این نسخه از تکرار موازی برای همه مشکلات حداکثر برش کار خواهد کرد یا خیر. براورمن گفت: «این به این معنی نیست که کار شما تمام شده است. "این فقط به این معنی است که شما به تجارت برگشته اید."

مینزر گفت: «پتانسیل زیادی در هندسه وجود دارد. "فقط این است که ما آن را به اندازه کافی درک نمی کنیم."