مدل هوش مصنوعی OpenAI بر فرضیه زمان نمایی (ETH) چالش میکشد
منتشرشده: · فناوری

یک مقالهٔ OpenAI با ارائهٔ برهان ریاضی، فرضیهٔ ۲۷ سالهٔ زمان نمایی (ETH) را بهصورت نظری رد میکند و پیامدهای آن را برای الگوریتمهای پیچیده بررسی میکند.
مدل هوش مصنوعی OpenAI با ارائهٔ برهان ریاضی، فرضیهٔ ۲۷ سالهٔ زمان نمایی (ETH) را بهصورت نظری چالش میکند.
پژوهشگران علوم کامپیوتر در دو دههٔ گذشته ابزارهای مختلفی برای سادهکردن مسائل پیچیده ساختهاند؛ الگوریتم «تقسیم و فهرست» رایان ویلیامز، روشهای جبری آندرئاس بیورکلوند، پژوهشهای کدهای مبتنی بر گرافهای انبساطی، و لم پراکندهسازی ایمپالیاجو، پاتوری و زین از جمله ایدههایی هستند که مقالهٔ OpenAI بر آنها تکیه میکند.
ETH در ربع قرن گذشته نقش ابزاری مشترک را بازی میکرد؛ دانشمندان معمولاً نمیتوانند ثابت کنند الگوریتم سریعتری برای یک مسئله وجود ندارد؛ اما با فرض ETH میتوانستند بگویند «اگر این مسئله سریعتر حل شود، 3‑SAT هم سریعتر حل میشود و ETH میگوید چنین چیزی ممکن نیست». به گفتهٔ OpenAI، صدها مقاله در نظریهٔ گراف، زیستشناسی محاسباتی، پایگاههای داده و هندسهٔ محاسباتی با همین منطق نتیجه گرفته بودند.
اگر ادعا درست باشد، دامنهٔ تاثیر ETH فراتر میرود. مقالهٔ OpenAI صراحتاً میگوید نتیجهٔ این برهان نسخهٔ قویتر، یعنی فرضیهٔ زمان نمایی قوی (SETH) و چند خویشاوند دیگرش را هم رد میکند.
SETH پایهٔ حوزهٔ پیچیدگی ریزدانه بود و برای مسائلی کاملاً روزمره کران تعیین میکرد؛ مثلاً اینکه فاصلهٔ ویرایشی، یعنی سنجش شباهت دو رشتهٔ DNA یا دو متن، احتمالاً خیلی سریعتر از الگوریتمهای امروزی محاسبهشدنی نیست.
رد ETH صدها مقالهٔ علمی را خودبهخود باطل نمیکند، اما اعتبار برخی از نتایج آنها را زیر سوال میبرد. الگوریتم هم پیامدهای مستقیم دیگری دارد؛ به ادعای مقاله، شمردن رنگآمیزیهای مجاز یک نقشه یا شمردن جورسازیهای کامل در یک شبکه، حالا در زمان زیر نمایی ممکن میشود.
رد فرضیهٔ ETH همانند تاثیر مشابهی خواهد داشت؛ گزارههای شرطی مقالههای قبلی همچنان از نظر منطقی درست باقی میمانند؛ اما شرطشان دیگر برقرار نیست. مقالهٔ OpenAI یادآوری میکند که بخشی از کرانها از فرضیههای ضعیفتری مانند حدس بردارهای متعامد نیز بهدست میآیند که شاید هنوز پابرجا باشند.
برهان جدید OpenAI، سوالی را مطرح میکند که آیا به حل یکی از مشهورترین معماهای حلنشدهٔ علوم کامپیوتر، یعنی P در برابر NP، نزدیک شدهایم؟ این معما پرسیده میکند آیا هر مسئلهای که بتوان جوابش را سریع بررسی کرد، لزوماً راهی هم برای سریع پیداکردن جواب دارد؟
الگوریتم جدید در دستهٔ روشهای زیر نمایی قرار میگیرد؛ یعنی با بزرگتر شدن مسئله، زمان اجرای آن از روشهای نمایی معمول آهستهتر افزایش مییابد. با این حال، هنوز با الگوریتمهای چندجملهای که معیار ریاضیِ حل سریع مسائل بهشمار میروند، فاصلهٔ زیادی دارد. کشف یک راه سریعتر برای حل مسئله، لزوماً به معنای یافتن راهی سریع برای حل همهٔ مسائل دشوار محاسباتی نیست.
از سوی دیگر، روش جدید برای خانوادهٔ مشخصی از مسائل SAT کار میکند که در آن تعداد متغیرهای هر شرط از حد ثابتی فراتر نمیرود. تبدیل یک مسئله به مسئلهٔ دیگر گاهی اندازهٔ آن را چنان افزایش میدهد که تمام مزیت الگوریتم جدید از بین میرود. نویسندگان مقاله نیز به این محدودیت اشاره کردهاند.