سدی از سال 1962 در علوم رایانه فرو میریزد
دور همیلتونی (Hamiltonian cycle) گشتی رفتوبرگشتی در یک شبکه است که هر نقطه را دقیقاً یک بار میبیند و به نقطهٔ شروع بازمیگردد. در شبکهای جهتدار، هر پیوند پیکانی است که فقط در یک جهت میتوان دنبالش کرد، مانند خیابانی یکطرفه. نسخهٔ وزندار این مسئله، مسئلهٔ فروشندهٔ دورهگردِ نامتقارن است.
تصمیمگیری دربارهٔ وجود چنین دوری مسئلهای دشوار و درسنامهای است. در 1962، ریچارد بلمن و، بهطور مستقل، مایکل هلد و ریچارد کارپ الگوریتمهایی مبتنی بر برنامهریزی پویا ارائه کردند که مسئله را برای شبکهای با n نقطه در زمانی حدود 2ⁿ حل میکنند (بهجز ضرایبی که تنها بهصورت چندجملهای رشد میکنند). بیش از شصت سال، هیچکس نتوانست روی شبکههای جهتدار عمومی بهطور بنیادی بهتر عمل کند.
پسرعموی بیجهت پیشتر فرو ریخته بود
برای شبکههایی با پیوندهای دوطرفه، آندرئاس بیورکلوند در 2014 با الگوریتمی تصادفی که در 1.657ⁿ اجرا میشود این سد را شکست؛ به نوشتهٔ مقاله، این کار جایزهٔ نرود EATCS–IPEC سال 2016 را برایش به ارمغان آورد. این هنوز سریعترین روش شناختهشده برای شبکههای بیجهت عمومی است. برای شبکههای جهتدار، پیشرفت تنها در حالتهای خاص — شبکههای دوبخشی، شبکههایی با پیوندهای اندک در هر نقطه — یا با فرض فرضیهای اثباتنشده، یعنی حدس رتبهٔ مجانبی اشتراسن، به دست آمد.
مرز تازه
توموهیرو کوآنا (Tomohiro Koana) از دانشگاه توکیو و سو کومابه (Soh Kumabe) از شرکت CyberAgent در توکیو، اکنون الگوریتمی تصادفی ارائه میکنند که مسئلهٔ جهتدار را در زمان زیر حل میکند:
O((375/196)ⁿ) = O(1.9133ⁿ)**.
برای شبکههای جهتدار عمومی، این نخستین بهبود در پایهٔ تابع نمایی از 1962 است.
شمردن به زوج و فرد
دشواری ظریف است. شمردن دورها در پیمانهٔ 2 — یعنی فقط دانستن اینکه تعدادشان فرد است یا زوج — پیشتر در زمانی کمتر از 2ⁿ ممکن بود. اما تعداد زوج و ناصفرِ دورها دقیقاً شبیه صفر به نظر میرسد. راهحل کلاسیک دادن وزنهای تصادفی به پیوندهاست تا در وزن کلِ معینی یک جواب یکتا شود (لم جداسازی، isolation lemma)؛ اما روش سریع شمارش زوجیت نمیتوانست با وزنها کار کند.
دستورالعمل نویسندگان، به زبان ساده:
- یک پیکان از دور را حدس بزن و به جای آن، مسیری از میان همهٔ نقطهها از یک سر آن پیکان به سر دیگرش جستوجو کن.
- هر پیکان را با احتمال 1/50 بهطور تصادفی حذف کن.
- در هر نقطه سه گروه از پیکانهای ورودی بساز و هر پیکان باقیمانده را در مجموعهای تصادفی و ناتهی از گروهها کپی کن.
- اگر گشتی وجود داشته باشد، با احتمال دستکم (49/50)ⁿ⁻¹ میتوان در هر نقطه یک گروه برگزید بهطوری که تعداد مسیرهای معتبر فرد باشد.
- به هر گروه — نه به هر پیکان — وزنی تصادفی بده. اکنون ترفند جداسازی کار میکند و حدود (50/49)ⁿ تکرار کافی است.
- هر تکرار شمارشهای زوجیافرد را در هر وزن کل در زمان (15/8)ⁿ محاسبه میکند، با استفاده از مجموع دترمینانهای ماتریسی از بیورکلوند، کاسکی و کوتیس و یک «خطیسازی» تصادفی که آرویند و گوروسوامی نیز به کار بردهاند.
این دو را ضرب کنید: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.
برهانی که ماشین تولید کرد
مقاله با اعلامیهای دربارهٔ هوش مصنوعی مولد به پایان میرسد: ChatGPT 6 Astra برهان قضیهٔ اصلی را تولید کرد و در نگارش پیشنویس دستنوشته کمک کرد. نویسندگان صورت گزارههای میانی را فراهم کردند، که خوانشی ترکیبیاتی از راهحل اصلی مدل به دست میدهند، سپس همه چیز را وارسی و بازنگری کردند و مسئولیت کامل را بر عهده میگیرند.
نتیجه نظری است — هیچ برنامهای اجرا نشد — و الگوریتم تصادفی است، با احتمال اندکی از خطا در هر دو جهت. میان 1.9133 برای خیابانهای یکطرفه و 1.657 برای دوطرفهها، شکافی پهن همچنان باز است.
