जोड़ने पर लक्ष्य बनाने वाली संख्याएँ चुनना, लगभग उन्हें पढ़ने जितनी तेज़ी से

यह एक ऐसी पहेली है जिसे कोई भी कह सकता है। आपके पास पूर्ण संख्याओं की एक सूची है — मान लीजिए 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 का समय — इनपुट पढ़ने से ज़्यादा नहीं। इस क्षेत्र के शोधकर्ताओं ने इसे इस कार्य-धारा की “सबसे अहम खुली समस्या” कहा था।

लक्ष्य से बाल-भर दूर

चीन के झेजियांग विश्वविद्यालय के लिन चेन, युचेन माओ और गुओचुआन झांग एक ऐसा एल्गोरिद्म देते हैं जो n + N^(1+ε) समय में चलता है, जहाँ ε पहले से तय कोई भी छोटी धनात्मक संख्या हो सकती है — 0.1, 0.01, 0.001। यह नियतात्मक है, ऋणात्मक संख्याएँ और दोहराए गए मान स्वीकार करता है, और एक गणितीय प्रमाण के साथ आता है। लेखक इस समय को लगभग-इष्टतम (near-optimal) कहते हैं।

परिणाम सदिशों (vectors) तक फैलता है: ऐसी वस्तुएँ चुनना कि कई जोड़ एक साथ अपने लक्ष्यों तक पहुँचें, d निर्देशांकों के लिए N^(d+ε) समय में। यह बदले में पूर्णांक प्रोग्रामिंग (integer programming) के बारे में कई समूहों द्वारा उठाए गए एक सवाल के एक हिस्से का जवाब देता है — ऐसे समीकरण-तंत्रों के पूर्ण-संख्या हल ढूँढना जिनके चर सीमित हों। दो परिणाम स्पष्ट रूप से निकाले गए हैं: संख्याओं के एक समूह को दो बराबर हिस्सों में बाँटना, और दो एक जैसी मशीनों के बीच काम यथासंभव बराबर बाँटना।

संख्याओं को एक ऊँचे आयाम में उठाना

मुख्य विचार ज्यामितीय है। यह पहले से पता था कि जब संख्याएँ घनी हों और लक्ष्य संभावित जोड़ों के दायरे के अच्छी तरह भीतर हो, तो समस्या आसान है। लेखकों का अवलोकन: संख्याओं का एक विरल समूह ऊँचे आयाम से देखने पर घना दिख सकता है।

उनका उदाहरण समूह {11, 12, 22, 24} है। 11 और 22 को पहले अक्ष पर एक क़दम और दो क़दम, और 12 और 24 को दूसरे अक्ष पर एक क़दम और दो क़दम के रूप में लिखिए। तब संभावित जोड़ एक छोटे 4-गुणा-4 वर्ग के हर बिंदु को भर देते हैं। लेकिन उस वर्ग को वापस एक रेखा पर दबा दीजिए — 11x + 12y की गणना करके — तो जोड़ सात अलग-अलग गुच्छे बनाते हैं जिनके बीच ख़ाली जगहें हैं, जो 0 और 69 के बीच बिखरे हैं। ख़ाली जगहें प्रक्षेपण (projection) का भ्रम हैं; दो आयामों में संरचना सरल है।

एल्गोरिद्म योगात्मक संयोजिकी (additive combinatorics) के परिणामों का उपयोग करके किसी भी इनपुट के लिए ऐसे ऊँचे-आयामी निर्देशांक बनाता है। “भरे हुए” क्षेत्र के भीतर जवाब मुफ़्त में मिल जाते हैं। केवल किनारे के पास के एक पतले क्षेत्र में असली मेहनत लगती है, जिसे एल्गोरिद्म छोटी समस्याओं में तोड़कर पुनरावर्ती (recursively) रूप से हल करता है। हर दौर उस क्षेत्र को तेज़ी से सिकोड़ता है, और कुल मिलाकर केवल स्थिर संख्या में नए आयाम ही जोड़े जाते हैं।

प्रमाण कैसे बना

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

अभी पूरी तरह अंतिम रेखा नहीं

घातांक ठीक 1 के बजाय 1 + ε है, और ε घटने के साथ छिपे अचर बढ़ते जाते हैं; आयामों की संख्या पर निर्भरता अनुकूलित नहीं की गई है। लेखक ख़ुद एल्गोरिद्म को “काफ़ी पेचीदा” बताते हैं। शोधपत्र सैद्धांतिक है: यह कोई कार्यान्वयन या बेंचमार्क प्रस्तुत नहीं करता।