कंप्यूटर विज्ञान में 1962 की एक दीवार गिरी

हैमिल्टनी चक्र किसी जाल में एक ऐसा पूरा चक्कर है जो हर बिंदु पर ठीक एक बार जाता है और शुरुआती बिंदु पर लौट आता है। निर्देशित (डायरेक्टेड) जाल में हर कड़ी एक तीर होती है जिस पर केवल एक ही दिशा में चला जा सकता है, एकतरफ़ा सड़क की तरह। इस समस्या का भारित रूप असममित ट्रैवलिंग सेल्समैन समस्या है।

यह तय करना कि ऐसा चक्र मौजूद है या नहीं, पाठ्यपुस्तकों की एक कठिन समस्या है। 1962 में रिचर्ड बेलमैन ने, और स्वतंत्र रूप से माइकल हेल्ड और रिचर्ड कार्प ने, डायनेमिक प्रोग्रामिंग एल्गोरिद्म दिए जो n बिंदुओं वाले जाल के लिए इसे लगभग 2ⁿ समय में हल करते हैं (केवल बहुपद की तरह बढ़ने वाले गुणकों को छोड़कर)। साठ से ज़्यादा वर्षों तक, सामान्य निर्देशित जालों पर कोई भी इससे मूलभूत रूप से बेहतर नहीं कर पाया।

अनिर्देशित चचेरा भाई पहले ही गिर चुका था

दोतरफ़ा कड़ियों वाले जालों के लिए, आंद्रेयास ब्यॉर्कलुंड ने 2014 में 1.657ⁿ में चलने वाले एक यादृच्छिक एल्गोरिद्म से यह दीवार तोड़ी थी; शोध-पत्र के अनुसार, इस काम के लिए उन्हें 2016 का EATCS–IPEC नेरोड पुरस्कार मिला। सामान्य अनिर्देशित जालों के लिए यह आज भी सबसे तेज़ ज्ञात एल्गोरिद्म है। निर्देशित जालों के लिए प्रगति केवल विशेष मामलों में हुई — द्विभाजित (बाइपार्टाइट) जाल, प्रति बिंदु कम कड़ियों वाले जाल — या एक अप्रमाणित परिकल्पना, स्ट्रासेन के अनंतस्पर्शी रैंक अनुमान (asymptotic rank conjecture), के तहत।

नई सीमा

टोक्यो विश्वविद्यालय के तोमोहिरो कोआना और टोक्यो की कंपनी CyberAgent के सोह कुमाबे अब एक यादृच्छिक एल्गोरिद्म देते हैं जो निर्देशित समस्या को इस समय में तय करता है:

O((375/196)ⁿ) = O(1.9133ⁿ)**।

सामान्य निर्देशित जालों के लिए, 1962 के बाद से यह घातांक के आधार में पहला सुधार है।

सम और विषम में गिनती

कठिनाई बारीक है। चक्रों को मॉड्यूलो 2 गिनना — यानी केवल यह जानना कि उनकी संख्या सम है या विषम — 2ⁿ से कम समय में पहले से संभव था। लेकिन चक्रों की एक सम, शून्येतर संख्या बिल्कुल शून्य जैसी ही दिखती है। इसका क्लासिक उपाय है कड़ियों को यादृच्छिक भार देना, ताकि किसी कुल भार पर एक हल अद्वितीय बन जाए (पृथक्करण प्रमेयिका, isolation lemma); लेकिन सम-विषम गिनने की तेज़ विधि भारों को सँभाल नहीं पाती थी।

लेखकों का नुस्ख़ा, सरल शब्दों में:

1. चक्र के एक तीर का अनुमान लगाओ, और उसकी जगह उस तीर के एक सिरे से दूसरे सिरे तक हर बिंदु से गुज़रने वाला रास्ता खोजो।
2. हर तीर को 1/50 की प्रायिकता से बेतरतीब ढंग से हटाओ।
3. हर बिंदु पर आने वाले तीरों के तीन समूह बनाओ, और बचे हुए हर तीर को समूहों के एक यादृच्छिक, अरिक्त समुच्चय में कॉपी करो।
4. अगर चक्कर मौजूद है, तो कम से कम (49/50)ⁿ⁻¹ की प्रायिकता से हर बिंदु के लिए एक समूह ऐसे चुना जा सकता है कि मान्य रास्तों की संख्या विषम हो।
5. हर समूह को — हर तीर को नहीं — एक यादृच्छिक भार दो। अब पृथक्करण की तरकीब काम करती है, और लगभग (50/49)ⁿ दोहराव काफ़ी होते हैं।
6. हर दोहराव (15/8)ⁿ समय में हर कुल भार पर सम-विषम गिनती निकालता है, जिसके लिए ब्यॉर्कलुंड, कास्की और कूटिस के मैट्रिक्स सारणिकों के योग और एक यादृच्छिक “रैखिकीकरण” का उपयोग होता है, जिसे अरविंद और गुरुस्वामी ने भी इस्तेमाल किया था।

दोनों को गुणा करें: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ।

मशीन से तैयार हुआ प्रमाण

शोध-पत्र जनरेटिव एआई पर एक घोषणा के साथ ख़त्म होता है: मुख्य प्रमेय का प्रमाण ChatGPT 6 Astra ने तैयार किया और पांडुलिपि का मसौदा बनाने में मदद की। लेखकों ने बीच के प्रस्तावों के कथन दिए, जो मॉडल के मूल हल की एक संचयात्मक (कॉम्बिनेटोरियल) व्याख्या देते हैं; फिर उन्होंने सब कुछ जाँचा और संशोधित किया, और पूरी ज़िम्मेदारी लेते हैं।

यह परिणाम सैद्धांतिक है — कोई प्रोग्राम नहीं चलाया गया — और एल्गोरिद्म यादृच्छिक है, जिसमें दोनों ओर त्रुटि की एक छोटी संभावना है। एकतरफ़ा सड़कों के लिए 1.9133 और दोतरफ़ा सड़कों के लिए 1.657 के बीच, एक बड़ा फ़ासला अब भी खुला है।