बेरीज जुळणाऱ्या संख्या निवडणे, जवळजवळ त्या वाचण्याइतक्याच वेगाने

हे एक कोडे आहे जे कोणीही मांडू शकतो. तुमच्याकडे पूर्ण संख्यांची एक यादी आहे — समजा 3, 9, 14, 20 — आणि एक लक्ष्य, समजा 23. त्यांपैकी काही अशा निवडता येतील का की त्यांची बेरीज नेमकी लक्ष्याएवढी होईल? (इथे हो: 3 + 20 किंवा 9 + 14.) हा आहे उपसंच-बेरीज (Subset Sum) प्रश्न, संगणकशास्त्रातील सर्वात मूलभूत प्रश्नांपैकी एक. शोधनिबंध त्याचे वर्णन एक मूलभूत NP-पूर्ण (NP-complete) प्रश्न असे करतो, अचूकपणे सोडवायला कठीण म्हणून ओळखल्या जाणाऱ्या प्रश्नांचे एक कुटुंब.

तरीही एक पळवाट आहे. संख्या फार मोठ्या नसतील, तर चतुर अल्गोरिदम त्यांच्या आकारावर अवलंबून असलेल्या वेळेत चालतात. 1957 मधील बेलमन यांची अभिजात पद्धत संख्यांची संख्या n आणि लक्ष्य t यांच्या गुणाकाराच्या प्रमाणात वेळ घेते. तेव्हापासून अल्गोरिदम सुधारत गेले आहेत:

• पिसिंजर (1999): n × N च्या प्रमाणात, जिथे N ही सर्वात मोठी संख्या आहे;
• ब्रिंगमन (2017): साधारण n + t;
• अनेक चमू (2021–2024): साधारण n + N^(5/3), मग n + N^(3/2).

अंतिम ध्येय होते साधारण n + N इतका वेळ — इनपुट वाचण्यापेक्षा फारसा अधिक नाही. या क्षेत्रातील संशोधकांनी त्याला या कार्यप्रवाहातील “सर्वात कळीचा अनुत्तरित प्रश्न” म्हटले होते.

ध्येयाच्या केसभर अंतरावर

चीनमधील झेजियांग विद्यापीठाचे लिन चेन (Lin Chen), युचेन माओ (Yuchen Mao) आणि गुओचुआन झांग (Guochuan Zhang) एक असा अल्गोरिदम देतात जो n + N^(1+ε) वेळेत चालतो, जिथे ε ही आधीच ठरवलेली कोणतीही लहान धन संख्या असू शकते — 0.1, 0.01, 0.001. तो निर्धारणात्मक (deterministic) आहे, ऋण संख्या आणि पुनरावृत्त मूल्ये स्वीकारतो, आणि त्याच्यासोबत गणितीय सिद्धता आहे. लेखक या वेळेला जवळजवळ इष्टतम (near-optimal) म्हणतात.

हा निकाल सदिशांपर्यंत विस्तारतो: अशा वस्तू निवडणे की अनेक बेरजा एकाच वेळी आपापल्या लक्ष्यांवर पोहोचतील, d निर्देशांकांसाठी N^(d+ε) वेळेत. त्यातून, पूर्णांक प्रोग्रामिंगविषयी (integer programming) अनेक गटांनी उपस्थित केलेल्या एका प्रश्नाचा काही भाग सुटतो — ज्यांचे चल मर्यादित आहेत अशा समीकरण-प्रणालींच्या पूर्ण-संख्या उकली शोधणे. दोन परिणाम स्पष्टपणे मांडले आहेत: संख्यांच्या एका संचाचे दोन समान अर्ध्या भागांत विभाजन करणे, आणि दोन एकसारख्या यंत्रांमध्ये कामांची शक्य तितकी समान वाटणी करणे.

संख्यांना उच्चतर मितीत उचलणे

मुख्य कल्पना भूमितीय आहे. हे आधीच माहीत होते की संख्या दाट असतील आणि लक्ष्य शक्य बेरजांच्या पल्ल्याच्या चांगले आत असेल, तर प्रश्न सोपा असतो. लेखकांचे निरीक्षण: संख्यांचा एक विरळ संच उच्चतर मितीतून पाहिल्यास दाट दिसू शकतो.

त्यांचे उदाहरण आहे {11, 12, 22, 24} हा संच. 11 आणि 22 पहिल्या अक्षावर एक पाऊल आणि दोन पावले म्हणून लिहा, आणि 12 आणि 24 दुसऱ्या अक्षावर एक पाऊल आणि दोन पावले म्हणून. मग शक्य बेरजा एका छोट्या 4-बाय-4 चौरसातील प्रत्येक बिंदू भरतात. पण तो चौरस पुन्हा एका रेषेवर दाबला — 11x + 12y मोजून — की बेरजा 0 आणि 69 दरम्यान विखुरलेले, मधे फटी असलेले सात वेगळे पुंजके बनतात. फटी हा प्रक्षेपणाचा भ्रम आहे; दोन मितींमध्ये रचना सोपी आहे.

अल्गोरिदम बेरीज-संयोजनशास्त्रातील (additive combinatorics) निकालांचा वापर करून कोणत्याही इनपुटसाठी असे उच्च-मितीय निर्देशांक तयार करतो. “भरलेल्या” प्रदेशाच्या आत उत्तरे फुकट मिळतात. फक्त कडेजवळच्या एका पातळ पट्ट्यालाच खरी मेहनत लागते, जिचे अल्गोरिदम छोट्या प्रश्नांमध्ये विभाजन करून ते पुनरावर्ती (recursively) पद्धतीने सोडवतो. प्रत्येक फेरीत तो पट्टा झपाट्याने आकुंचन पावतो, आणि नव्या मिती नेहमी एका स्थिर संख्येइतक्याच जोडल्या जातात.

सिद्धता कशी उभारली गेली

शोधनिबंधाची सुरुवात एका “AI अस्वीकरणाने” होते. लेखकांनी या प्रश्नाच्या दाट, बहुमितीय आवृत्त्यांवरील आपल्या अलीकडच्या कामावर आधारित, मुख्य सिद्धता-मार्ग स्वतः रचला. मग त्यांनी या कल्पनांचे संपूर्ण गणितीय सिद्धतांमध्ये रूपांतर करण्यासाठी GPT Astra Ultra हे AI मॉडेल वापरले. ते अनेक उपप्रमेयांवर (lemmas) अडकले, जी लेखकांच्या कल्पनांनी सोडवली गेली; एक सार्वजनिक संशोधन-टिपण त्या संवादांची नोंद ठेवते. मूलभूत यादृच्छिक (randomised) अल्गोरिदम पूर्ण झाल्यावर मॉडेलने त्याचा विस्तार निर्धारणात्मक, बहुमितीय आवृत्त्यांपर्यंत “लेखकांच्या कोणत्याही मार्गदर्शनाशिवाय” केला. मॉडेलने शोधनिबंधाचा मसुदाही तयार केला आणि, लेखक लिहितात, Lean 4 सिद्धता-सहायकातील सिद्धतेद्वारे त्याचे मुख्य निकाल पडताळले. मजकुराची संपूर्ण जबाबदारी लेखक घेतात.

अजून अंतिम रेषा नव्हे

घातांक नेमका 1 नसून 1 + ε आहे, आणि ε लहान होईल तसे लपलेले स्थिरांक वाढतात; मितींच्या संख्येवरील अवलंबित्व इष्टतम केलेले नाही. लेखक स्वतःच अल्गोरिदमचे वर्णन “बराच गुंतागुंतीचा” असे करतात. शोधनिबंध सैद्धांतिक आहे: त्यात कोणतीही अंमलबजावणी किंवा बेंचमार्क नोंदवलेला नाही.