الگوریتم‌های کهکشانی، فرضیه زمان نمایی و گم کردن مسیر اصلی در علوم کامپیوتر

نگاهی به مفهوم کارایی در الگوریتم‌ها

بحث درباره کارایی الگوریتم‌ها سابقه طولانی دارد. در سال ۱۹۶۵، Jack Edmonds تلاش کرد تا برای اولین بار مفهوم «الگوریتم خوب» یا کارآمد را تعریف کند. او دریافت که بررسی تمام حالت‌های ممکن (جستجوی فراگیر یا brute-force) برای حل مسائلی مانند matching در گراف‌ها زمان‌بر و از نظر نمایی (exponential) رشد می‌کند. او توانست الگوریتمی با زمان اجرای مرتبه چهارم (n^4) ارائه دهد که بسیار بهتر از روش‌های نمایی بود.

کمی بعد، Richard Karp و دیگران زمان «چندجمله‌ای» (polynomial time) را به عنوان استاندارد طلایی برای کارایی پذیرفتند. ایده کلی این بود که زمان اجرا باید با توانی از اندازه ورودی محدود شود. با این حال، زمان چندجمله‌ای هم خالی از اشکال نیست؛ مثلاً یک الگوریتم با زمان اجرای n^1000 از نظر تئوری چندجمله‌ای است، اما در عمل کاملاً بی‌فایده خواهد بود.

الگوریتم‌های کهکشانی و جنجال اخیر OpenAI

اعتماد کورکورانه به تحلیل مجانب (asymptotic analysis) باعث ظهور «الگوریتم‌های کهکشانی» (galactic algorithms) شده است؛ راهکارهایی که روی کاغذ کارآمدند، اما زمان اجرای آن‌ها به قدری نجومی است که پیاده‌سازی‌شان در جهان واقعی غیرممکن است.

به تازگی، مقاله‌ای از OpenAI پیرامون مسئله Satisfiability (یکی از معروف‌ترین مسائل NP-complete) سر و صدای زیادی به پا کرد و در شبکه‌های اجتماعی به عنوان بزرگ‌ترین دستاورد نظری دهه‌های اخیر معرفی شد. این مقاله ادعا می‌کرد که به زمان «زیرنمایی» (subexponential time) دست یافته است. اما بررسی دقیق‌تر متن (و کمک گرفتن از ابزارهای هوش مصنوعی) نشان داد که یک نکته پنهان بزرگ وجود دارد:

• الگوریتم جدید تا پیش از رسیدن تعداد متغیرها به یک آستانه غیرقابل تصور (عددی بسیار بزرگ‌تر از کل اتم‌های موجود در جهان)، در واقع همان جستجوی فراگیر و نمایی قدیمی را اجرا می‌کند.
• این دستاورد بزرگ تئوریک، هیچ کاربردی در دنیای واقعی ندارد و تنها در «محله‌ای ناشناخته در بی‌نهایت» بهینه‌تر عمل می‌کند.

چرا این موضوع برای مهندسان نرم‌افزار مهم است؟

این مقاله یادآوری می‌کند که تئوری پیچیدگی محاسباتی گاهی مسیر خود را گم کرده و از واقعیت‌های مهندسی فاصله گرفته است. در حالی که محققان روی مرزهای دوردست بی‌نهایت تمرکز می‌کنند، مهندسان در دنیای واقعی با ابزارهای عملی توانسته‌اند مسائل صنعتی بسیار بزرگ با میلیون‌ها متغیر را به خوبی و با کارایی بالا حل کنند.

نگاه جامعه Hacker News

بحث درباره این مقاله در Hacker News با نظرات متفاوتی همراه بود:

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