میان‌بری که قرار نبود وجود داشته باشد؛ هوش مصنوعی و حل معمای ۲۷ساله دنیای کامپیوتر
مدل هوش مصنوعی OpenAI با ارائه‌ی برهان ریاضی، فرضیهی ۲۷ساله‌ی زمان نمایی (ETH) درباره‌ی محدودیت سرعت حل مسائل پیچیده‌‌ی محاسباتی را به‌چالش کشید.
مدل هوش مصنوعی OpenAI با ارائه‌ی برهان ریاضی، فرضیهی ۲۷ساله‌ی زمان نمایی (ETH) درباره‌ی محدودیت سرعت حل مسائل پیچیده‌‌ی محاسباتی را به‌چالش کشید.
تصور کنید ربع قرن پیش قاعده‌ای درباره‌ی محدودیت کامپیوترها پیشنهاد داده‌اید. همکارانتان آن را پذیرفته‌اند، صدها مقاله براساسش نوشته‌اند و هیچ‌کس هم نتوانسته خلافش را ثابت کند. حالا یک روز خبر می‌رسد که مدل‌های هوش مصنوعی قاعده‌ی شما را از اساس رد کرده‌اند و از شما می‌خواهند داور همین ادعا باشید.
راسل ایمپالیاجو و راماموهان پاتوری، دو استاد علوم کامپیوتر دانشگاه کالیفرنیا در سن‌دیگو، امروز دقیقاً در چنین موقعیتی قرار دارند. OpenAI روز ۲۶ اکتبر ۲۰۲۶ اعلام کرد یکی از مدل‌های داخلی‌اش «فرضیهی زمان نمایی» یا ETH را رد کرده است؛ فرضیه‌ای که همین دو دانشمند به‌همراه فرانسیس زین ارائه داده بودند. به گفته‌ی شرکت، مدل هوش مصنوعی، برهان را ۱۶ اکتبر پیدا کرد و یک روز بعد، استدلال آن در سامانه‌ی اثبات رسمی Lean بازنویسی و به‌شکل ماشینی بررسی شد.
یکی از ابزارهای اصلی برهان را قضیه‌ای به‌نام «لم پراکنده‌سازی» می‌دانند؛ قضیه‌ای که خود ایمپالیاجو، پاتوری و زین در سال ۲۰۰۱ برای تقویت مبانی فرضیه‌شان ارائه کرده بودند. حالا ۲۵ سال بعد، همان ابزار در برهانی به‌کار رفته است که فرضیهی آن‌ها را رد می‌کند. درواقع پژوهشگران برای رد فرضیهی ETH از یکی از دستاوردهای علمی سازندگان خودش استفاده کرده‌اند.
حتی اگر صحت ادعای اوپن‌ای‌آی تایید شود، فردا صبح هیچ کامپیوتری سریع‌تر کار نمی‌کند، هیچ رمزی نمی‌شکند و هیچ اپلیکیشنی تغییر نمی‌کند. پس چرا دنیای علوم کامپیوتر با شنیدن خبر این‌قدر هیجان‌زده شد؟ برای درک اهمیت فرضیهی زمانی نمایی، باید سراغ یکی از ساده‌ترین و درعین‌حال سرسخت‌ترین معماهای محاسبات برویم.
فرض کنید پشت ردیفی از کلیدهای برق نشسته‌اید و هر کلید فقط می‌تواند روشن باشد یا خاموش، حالت میانه‌ای در کار نیست. فهرستی از شرط‌ها را هم به دستتان داده‌اند و هر شرط سه کلید را نام می‌برد؛ مثلاً «یا A روشن باشد، یا B خاموش، یا C روشن»، یا «یا کلید اول خاموش باشد، یا کلید چهارم یا پنجم روشن باشد.»
برای برآورده‌شدن هر شرط، کافی است دست‌کم یکی از سه گزینه‌ی آن درست باشد؛ اما آیا می‌توان کلیدها را طوری تنظیم کرد که تمام شرط‌ها هم‌زمان برقرار شوند؟ دانشمندان علوم کامپیوتر این معما را «3-SAT» می‌نامند. در زبان منطق، هر کلید یک متغیر به شمار می‌رود که فقط دو حالت دارد؛ درست یا نادرست.
مسئله‌ی 3-SAT شاید در نگاه اول شبیه بازی‌های فکری به‌نظر برسد؛ اما یکی از مشهورترین مسائل «NP-کامل» در علوم کامپیوتر محسوب می‌شود. اگر کسی روشی واقعاً سریع برای حلش پیدا کند، هزاران مسئله‌ی بسیار سخت دیگر، از زمان‌بندی پروازها تا طراحی تراشه، با همان روش حل می‌شوند.
دشواری مسئله به تعداد حالت‌های ممکن برمی‌گردد. با اضافه‌شدن هر کلید، تعداد چیدمان‌ها دو برابر می‌شود؛ برای مثال ده کلید، ۱۰۲۴ حالت مختلف دارند، چهل کلید بیش از هزار میلیارد حالت و صد کلید عددی ۳۱ رقمی. در ریاضیات به این افزایش سریع، رشد نمایی می‌گویند و آن را با فرمول ۲ به توان n نشان می‌دهند؛ جایی که n تعداد کلیدهاست.
فرضیهی ETH می‌گفت هیچ الگوریتمی نمی‌تواند رشد نمایی زمان حل مسئله‌ی 3-SAT را به‌کلی از میان بردارد
البته الگوریتم‌های پیشرفته برای پیداکردن پاسخ، همه‌ی حالت‌ها را یکی‌یکی امتحان نمی‌کنند و با حذف هوشمندانه‌ی گزینه‌های بی‌فایده، تعداد حالت‌هایی را که باید بررسی شوند به‌شدت کاهش می‌دهند. بهترین روش‌های شناخته‌شده به‌جای زمانی در حدود (2ⁿ)، در زمانی حدود (1.3ⁿ) به پاسخ می‌رسند؛ اما (1.3ⁿ) هم رشد نمایی دارد؛ هرچند پایه‌ی توان کوچک‌تر شده است، ولی بازهم با افزایش تعداد کلیدها، زمان محاسبه همچنان با سرعتی صعودی، بالا می‌رود.
اواخر دهه‌ی ۱۹۹۰، ایمپالیاجو و پاتوری فرضیه‌ای مطرح کردند که می‌گفت شاید نتوان هرگز از رشد نمایی زمان محاسبه گریخت. این حدس علمی که فرضیهی زمان نمایی یا ETH نام گرفت، می‌گوید هیچ الگوریتمی نمی‌تواند مسئله‌ی 3-SAT را در همه‌ی موارد با زمانی کمتر از رشد نمایی حل کند؛ به‌بیان ساده‌تر، شاید بتوان پایه‌ی توان را از ۲ به عددی کوچک‌تر کاهش داد؛ اما نمی‌توان رشد نمایی را به‌کلی از میان برد.
برای بررسی ETH و استدلالی که خلافش را ثابت می‌کند، باید تمایزی ظریف را جدی بگیریم. فرض کنید الگوریتمی پیدا شود که به‌جای زمان 2ⁿ، مسئله را در زمان ⁽ⁿ/¹⁰⁰⁰⁾2 حل کند. چنین پیشرفتی از نظر عملی فوق‌العاده خواهد بود؛ اما همچنان فرضیهی ETH را نقض نمی‌کند؛ چون توان همچنان کسری ثابت از n باقی می‌ماند و با بزرگ‌شدن مسئله، هم‌پای n رشد می‌کند. درواقع زمان محاسبه همچنان به‌صورت نمایی افزایش می‌یابد، هرچند کندتر.
حالا فرض کنید الگوریتمی پیدا شود که با بزرگ‌ترشدن مسئله، زمان محاسبه‌اش بسیار کندتر از چیزی افزایش یابد که ETH پیش‌بینی می‌کند؛ مثلا الگوریتمی توانش نه n/۱۰۰۰، بلکه n تقسیم بر ریشه‌ی دوم لگاریتم n باشد. مخرج این کسر خیلی آرام بزرگ می‌شود؛ برای مسئله‌ای با یک میلیون متغیر، فقط به حدود ۳٫۷ می‌رسد. ریاضی‌دان‌ها به این نوع رشد، زیرنمایی می‌گویند.
در روش قبلی، زمان محاسبه همچنان با آهنگ نمایی افزایش می‌یافت؛ اما در روش جدید، هرچه مسئله بزرگ‌تر شود، زمان محاسبه در مقایسه با روش‌های نمایی، بسیار کندتر افزایش می‌یابد، یا فاصله‌اش از رشد نمایی معمول بیشتر و بیشتر می‌شود؛ درست همان چیزی که فرضیهی ETH امکان آن را برای حل 3-SAT رد می‌کند.
الگوریتم جدید رشد زمان محاسبه را از نمایی به زیرنمایی کاهش می‌دهد؛ همان چیزی که ETH ناممکن می‌دانست
فرضیهی ETH می‌گفت چنین الگوریتمی برای حل 3-SAT وجود ندارد؛ پس برای رد کردن فرضیه لازم نیست کسی 3-SAT را در چند ثانیه حل کند؛ کافی‌ست الگوریتمی پیدا کند که زمان محاسبه‌اش از نوع زیرنمایی باشد و مخرج توانش، هرچند کُند، بی‌وقفه رشد کند. اوپن‌ای‌آی دقیقاً از دست‌یافتن به چنین روشی خبر می‌دهد.
به گفته‌ی رایان ویلیامز، یکی از داوران پژوهش، الگوریتم جدید زمان محاسبه را به حدود ۲ به توانِ n تقسیم بر لگاریتم n به توانِ اندکی بیشتر از یک‌دوم کاهش می‌دهد؛ بنابراین الگوریتم با بزرگ‌ترشدن مسئله، از رشد نماییِ موردانتظار ETH فاصله می‌گیرد؛ هرچند ممکن است حل مسائل بسیار بزرگ همچنان زمان فوق‌العاده زیادی ببرد.
بخش جالب برهانی که اوپن‌ای‌آی برای رد فرضیهی ETH معرفی می‌کند، به شیوه‌ی حل مسئله برمی‌گردد؛ زیرا الگوریتم صرفا بررسی نمی‌کند که آیا می‌توان کلیدها را طوری تنظیم کرد که همه‌ی شرط‌ها برقرار شوند یا نه؛ بلکه تعداد دقیق چیدمان‌های درست را هم محاسبه می‌کند. طبیعتا شمردن تمام پاسخ‌های درست، از یافتن یک پاسخ دشوارتر خواهد بود.
ریاضی‌دانان نسخه‌ی شمارشی مسئله را #SAT می‌نامند؛ البته اگر تعداد پاسخ‌های درست را بدانیم، پاسخ پرسش ساده‌تر هم روشن می‌شود. اگر تعداد صفر باشد، هیچ راه‌حلی وجود ندارد؛ اما اگر بیشتر از صفر باشد، یعنی دست‌کم یک راه‌حل داریم؛ بدین‌ترتیب، اوپن‌ای‌آی برای پاسخ‌دادن به پرسشی ساده‌تر، الگوریتمی معرفی می‌کند که از عهده‌ی مسئله‌ای دشوارتر هم برمی‌آید.
الگوریتم اوپن‌ای‌آی تعداد تمام پاسخ‌های درست را محاسبه می‌کند
ایده‌ی کلی را می‌توانید این‌طور در نظر بگیرید که پژوهش ابتدا هر شرط منطقی را به عبارتی ریاضی تبدیل می‌کند که برای یک ترکیب سازگار، مقدارِ یک و برای ترکیب ناسازگار، مقدارِ صفر می‌گیرد. اگر عبارت‌های همه‌ی شرط‌ها را در هم ضرب کنیم، پاسخ‌هایی که حتی یکی از شرط‌ها را نقض می‌کنند، حذف می‌شوند. جمع نتیجه روی تمام ترکیب‌ها، تعداد پاسخ‌های معتبر را می‌دهد.
الگوریتم قطعی کار می‌کند، یعنی به انتخاب تصادفی متکی نیست و باوجود زمان اجرای طولانی، حافظه‌ای بیش‌از چندجمله‌ای مصرف نمی‌کند. مقاله‌ای ۶۷ صفحه‌ای که همراه اعلامیه‌ی اوپن‌ای‌آی منتشر شد، ایده را در چند گام توضیح می‌دهد.
گام اول به یک مشاهده‌ی ساده برمی‌گردد. اگر بتوان کلیدها را به گروه‌های کوچکی تقسیم کرد که هیچ شرطی میانشان پل نزند، تعداد کل جواب‌ها برابر حاصل‌ضرب تعداد جواب‌های هر گروه می‌شود. شمردن ده گروه ده‌تایی به‌جای یک گروه صدتایی، کار را از عددی ۳۱ رقمی به حدود ده‌هزار حالت می‌رساند.
اما مسئله‌های واقعی هرگز این‌قدر مرتب از هم جدا و تقسیم نمی‌شوند و نمی‌توان جواب‌های هر گروه را مستقل از بقیه شمرد. الگوریتم اوپن‌ای‌آی برای حل مشکل، به‌جای جداکردن مستقیم گروه‌ها، شکل مسئله را با یک پارامتر کمکی تغییر می‌دهد. در این نسخه‌ها، ارتباط میان گروه‌ها به چند مقدار مشترک محدود می‌شود. وقتی مقدارها را مشخص کنیم، می‌توانیم جواب‌های هر گروه را جداگانه بشماریم. سپس الگوریتم با استفاده از نتایج شمارش‌ها، تعداد جواب‌های مسئله‌ی اصلی را به‌دست می‌آورد.
الگوریتم قطعی کار می‌کند و به انتخاب تصادفی متکی نیست
در گام آخر، الگوریتم باید از جواب مسئله‌های ساده‌تر به جواب مسئله‌ی اصلی برسد. اینجا یک ویژگی ریاضی به کمکش می‌آید، تعداد جواب‌ها در نسخه‌های تغییریافته‌ی مسئله، از رابطه‌ای مشخص پیروی می‌کند که ریاضی‌دانان آن را چندجمله‌ای می‌نامند.
اگر مقدار رابطه را در چند نقطه‌ی مناسب بدانیم، می‌توانیم مقدارش را در نقطه‌ای دیگر هم دقیقاً محاسبه کنیم؛ حتی اگر محاسبه‌ی مستقیم در آن نقطه بسیار دشوار باشد. الگوریتم از همین ویژگی استفاده می‌کند تا با کنار هم گذاشتن نتایج محاسبات آسان‌تر، تعداد جواب‌های مسئله‌ی اصلی را به‌دست آورد؛ درست مثل‌اینکه ارتفاع قله‌ای دست‌نیافتنی را از روی چند نقطه‌ی دامنه و شکل دقیق منحنی آن به‌دست آوریم.