कंप्यूटिंग और एआईप्रीप्रिंटसिद्धांतपढ़ने में 4 मिनट

वर्जित तुलनाओं के साथ छँटाई, लगभग उतनी ही तेज़

n वस्तुओं को दो-दो की तुलना करके क्रम में लगाने के लिए, लगभग n log n तुलनाएँ आवश्यक भी हैं और पर्याप्त भी। लेकिन यह मानकर चलता है कि किन्हीं भी दो वस्तुओं की तुलना की जा सकती है।

अक्सर ऐसा नहीं हो सकता। लेखकों ने 2011 के एक शोधपत्र से एक उदाहरण लिया है: कई उम्मीदवार एक ही नौकरी के लिए आवेदन करते हैं, और हर एक के अपने संदर्भदाता (references) हैं। दो उम्मीदवारों की तुलना तभी की जा सकती है जब कोई संदर्भदाता दोनों को जानता हो। अनुमत तुलनाएँ एक जाल बनाती हैं, एक ग्राफ़ (graph): हर वस्तु एक बिंदु है, हर अनुमत तुलना एक कड़ी। असली क्रम छिपा हुआ है, लेकिन इस बात की गारंटी है कि ग्राफ़ में वह मौजूद है, एक ऐसे पथ के रूप में जो हर वस्तु को अगली वस्तु से जोड़ता है। प्रश्न: क्रम को वापस पाने में कितनी तुलनाएँ लगती हैं? यही है सामान्यीकृत छँटाई (generalized sorting)।

सामान्य तरकीबें क्यों विफल होती हैं

क्लासिक एल्गोरिद्म चुनाव की स्वतंत्रता पर निर्भर करते हैं। QuickSort एक “पिवट” (pivot) चुनता है और उसकी तुलना ज़्यादातर अन्य वस्तुओं से करता है, लेकिन किसी मनमाने ग्राफ़ में शायद कोई भी वस्तु ज़्यादातर अन्य वस्तुओं से जुड़ी न हो। MergeSort वस्तुओं को समूहों में बाँटता है और हर समूह को छाँटता है, लेकिन हो सकता है कोई समूह अपने-आप में छाँटा ही न जा सके: अंतिम क्रम में पड़ोसी दो वस्तुओं का उस समूह के भीतर जुड़ा होना ज़रूरी नहीं। और भी मूलभूत रूप से, साधारण छँटाई में हमेशा कोई ऐसी तुलना उपलब्ध होती है जो संभावित क्रमों के एक अच्छे-ख़ासे हिस्से को ख़ारिज कर देती है; सीमित तुलनाओं के साथ, शायद ऐसी कोई तुलना न हो।

प्रगति धीमी रही। 2011 में, झीयी हुआंग (Zhiyi Huang), संपत कन्नन (Sampath Kannan) और संजीव खन्ना (Sanjeev Khanna) ने एक ऐसी विधि खोजी जिसमें लघुगणकीय गुणकों (logarithmic factors) को छोड़कर लगभग n¹·⁵ तुलनाएँ लगती थीं, और तब से मनमाने ग्राफ़ों के लिए यही सीमा बनी रही। उन्होंने यह तक पूछा कि क्या यह समस्या साधारण छँटाई से मूलभूत रूप से कठिन हो सकती है, जिसमें n की 1 से बड़ी घात जितनी तुलनाओं की ज़रूरत हो।

पहले अनुमान, सुधार बाद में

न्यूयॉर्क यूनिवर्सिटी के संजीव खन्ना, हार्वर्ड यूनिवर्सिटी के ऐरन पुटरमैन (Aaron Putterman) और जुनकाई सॉन्ग (Junkai Song), जो इसी तरह न्यूयॉर्क यूनिवर्सिटी से हैं, ने अब उस प्रश्न का उत्तर दिया है: नहीं। उनका यादृच्छिक (randomised) एल्गोरिद्म किसी भी ग्राफ़ पर औसतन लगभग n log⁴ n तुलनाओं में छँटाई करता है — साधारण छँटाई से केवल कुछ लघुगणकीय गुणक ऊपर। और, उनके शब्दों में, यह “अपेक्षाकृत सरल” है। हालाँकि यह लाभ सैद्धांतिक है: प्रमाण के स्थिरांक बहुत विशाल हैं (2³² जैसे गुणक), इसलिए यह बढ़त केवल बहुत बड़े n के लिए दिखती है।

यह एक ज्ञात परिणाम पर आधारित है: अगर कोई आपको हर कड़ी की दिशा का एक अनुमान थमा दे, जो उनमें से w पर ग़लत हो, तो क्रम को लगभग n log n + w तुलनाओं में वापस पाया जा सकता है। इसलिए काम यह बन जाता है कि कम तुलनाओं से कम ग़लतियों वाला अनुमान तैयार किया जाए। मुख्य चरण:

  • एक मोटा पहला अनुमान। जुड़ी हुई जोड़ियों के एक यादृच्छिक नमूने की तुलना कीजिए और उत्तरों से संगत कोई भी क्रम चुन लीजिए। इसमें कई ग़लतियाँ होती हैं, लेकिन बहुत ज़्यादा नहीं।
  • ग़लतियों को सुधारने के बजाय अलग कीजिए। ग़लत अनुमानों को ठीक करने के बजाय, एल्गोरिद्म ग्राफ़ के उन हिस्सों को खोजता है जहाँ ग़लतियाँ औसत से ज़्यादा घनी हैं और उन्हें अलग रख देता है। हर दौर बची हुई ग़लतियों को, अपेक्षित मान में (in expectation), चार गुना घटा देता है।
  • बाद में लौटिए। अलग रखी गई कड़ियों को बाद के एक चरण में निपटाया जाता है। हर चरण अब भी लंबित कड़ियों में से कम से कम आधी का निपटारा कर देता है, इसलिए दस लाख कड़ियों के लिए लगभग बीस चरण काफ़ी हैं।

मशीनों के साथ खोजा गया प्रमाण

शोधपत्र का AI-प्रकटीकरण (AI disclosure) असामान्य रूप से विस्तृत है। उसमें कहा गया है कि ChatGPT 6-Astra “बेहतर सीमाओं (bounds) को सिद्ध करने में अनिवार्य था”। एक मॉडल ने पहले लगभग n¹·³³ तुलनाओं वाला एक एल्गोरिद्म खोजा, फिर अटक गया। लेखकों ने इसे n¹·² तक पहुँचाया; फिर, कई हफ़्तों में दर्जनों बार प्रॉम्प्ट किए जाने पर, मॉडलों ने क्रमिक सुधार खोजे — n^(10/9), n^(17/16), n^(19/18) — और अंततः लगभग-रैखिक (near-linear) एल्गोरिद्म तक पहुँचे। लेखकों ने यह भी जोड़ा है कि यह स्पष्ट नहीं है कि उनका अपना मध्यवर्ती चरण उस अंतिम खोज के लिए अनिवार्य था या नहीं।

अभी क्या खुला है

परिणाम तुलनाओं को गिनता है, गणना-समय को नहीं: अपने मौजूदा रूप में, एल्गोरिद्म बहुपद समय (polynomial time) में नहीं चलता, जबकि 2011 की विधि चलती थी। लेखकों ने तीन खुले प्रश्न गिनाए हैं: क्या बचे हुए लघुगणकीय गुणक हटाए जा सकते हैं, क्या यादृच्छिकता के बिना कोई एल्गोरिद्म उतना ही अच्छा कर सकता है, और क्या कोई कुशल एल्गोरिद्म तुलनाओं की उसी संख्या तक पहुँच सकता है — या n¹·⁵ को पार भी कर सकता है।