संगणकशास्त्रातील 1962 चा अडथळा कोसळला

हॅमिल्टनी चक्र (Hamiltonian cycle) म्हणजे जाळ्यातील प्रत्येक बिंदूला नेमकी एकदा भेट देऊन सुरुवातीच्या बिंदूकडे परत येणारी फेरी. दिष्ट (directed) जाळ्यात प्रत्येक दुवा हा एकेरी रस्त्याप्रमाणे फक्त एकाच दिशेने जाता येणारा बाण असतो. या समस्येची भारित (weighted) आवृत्ती म्हणजे असममित प्रवासी विक्रेता समस्या (asymmetric travelling salesman problem).

असे चक्र अस्तित्वात आहे का हे ठरवणे ही पाठ्यपुस्तकातील एक कठीण समस्या आहे. 1962 मध्ये रिचर्ड बेलमन यांनी, आणि स्वतंत्रपणे मायकेल हेल्ड व रिचर्ड कार्प यांनी, n बिंदूंच्या जाळ्यासाठी ती सुमारे 2ⁿ वेळेत (फक्त बहुपदी गतीने वाढणारे घटक वगळता) सोडवणारे गतिक-आयोजन (dynamic programming) अल्गोरिदम दिले. साठहून अधिक वर्षे, सर्वसाधारण दिष्ट जाळ्यांवर कोणालाही यापेक्षा मूलभूतरीत्या चांगले करता आले नाही.

अदिष्ट चुलतभाऊ आधीच कोसळला होता

दुतर्फा दुवे असलेल्या जाळ्यांसाठी आंद्रेआस ब्यॉर्कलुंड यांनी 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ⁿ.

यंत्राने निर्माण केलेली सिद्धता

शोधनिबंधाच्या शेवटी जनरेटिव्ह AI बाबत एक जाहीर निवेदन आहे: मुख्य प्रमेयाची सिद्धता ChatGPT 6 Astra ने निर्माण केली आणि हस्तलिखिताचा मसुदा तयार करण्यास मदत केली. लेखकांनी मधल्या विधानांची (propositions) मांडणी पुरवली, जी प्रतिरूपाच्या मूळ उत्तराचे संयोजनशास्त्रीय वाचन देतात; मग सर्व काही तपासले, सुधारले आणि त्याची पूर्ण जबाबदारी घेतली.

हा निकाल सैद्धांतिक आहे — कोणताही प्रोग्राम चालवला गेला नाही — आणि अल्गोरिदम यादृच्छिक आहे, ज्यात दोन्ही बाजूंनी चूक होण्याची थोडी शक्यता आहे. एकेरी रस्त्यांसाठीच्या 1.9133 आणि दुतर्फा रस्त्यांसाठीच्या 1.657 यांच्यामध्ये अजूनही मोठी दरी उघडी आहे.