निषिद्ध तुलनांसह क्रमवारी, जवळजवळ तितक्याच वेगाने
n वस्तूंची एका वेळी दोन-दोन अशी तुलना करून त्या क्रमाने लावण्यासाठी, सुमारे n log n तुलना आवश्यकही असतात आणि पुरेशाही. पण हे गृहीत धरते की कोणत्याही दोन वस्तूंची तुलना करता येते.
अनेकदा ती करता येत नाही. लेखक 2011 च्या एका शोधनिबंधातील उदाहरण उसने घेतात: अनेक उमेदवार एकाच नोकरीसाठी अर्ज करतात, आणि प्रत्येकाचे काही संदर्भदाते असतात. एखादा संदर्भदाता दोघांनाही ओळखत असेल, तरच दोन उमेदवारांची तुलना करता येते. परवानगी असलेल्या तुलना एक जाळे, एक आलेख (graph), तयार करतात: प्रत्येक वस्तू एक बिंदू, प्रत्येक परवानगी असलेली तुलना एक दुवा. खरा क्रम लपलेला असतो, पण आलेखात तो असण्याची हमी असते, प्रत्येक वस्तूला पुढच्या वस्तूशी जोडणाऱ्या एका मार्गाच्या रूपात. प्रश्न असा: तो क्रम परत मिळवायला किती तुलना लागतात? हीच सामान्यीकृत क्रमवारी (generalized sorting).
नेहमीच्या युक्त्या का अपयशी ठरतात
अभिजात अल्गोरिदम निवडीच्या स्वातंत्र्यावर अवलंबून असतात. QuickSort एक “पिव्हट” (pivot) निवडतो आणि त्याची तुलना इतर बहुतेक वस्तूंशी करतो, पण एखाद्या मनमानी आलेखात इतर बहुतेक वस्तूंशी जोडलेली एकही वस्तू नसू शकते. MergeSort वस्तूंना गटांत विभागतो आणि प्रत्येक गटाची क्रमवारी लावतो, पण एखाद्या गटाची स्वतंत्रपणे क्रमवारी लावता येईलच असे नाही: अंतिम क्रमात शेजारी असलेल्या दोन वस्तू त्या गटात एकमेकांशी जोडलेल्या असतीलच असे नाही. अधिक मूलभूतपणे, सामान्य क्रमवारीत नेहमीच अशी एक तुलना उपलब्ध असते जी शक्य क्रमांपैकी बऱ्याच मोठ्या भागाला बाद ठरवते; मर्यादित तुलनांसह, अशी एकही तुलना नसू शकते.
प्रगती मंद होती. 2011 मध्ये, झियी हुआंग (Zhiyi Huang), संपत कन्नन (Sampath Kannan) आणि संजीव खन्ना (Sanjeev Khanna) यांनी सुमारे n¹·⁵ तुलना वापरणारी एक पद्धत शोधली, लॉगरिदमीय गुणक (logarithmic factors) वगळता, आणि मनमानी आलेखांसाठी ती मर्यादा तेव्हापासून टिकून राहिली. त्यांनी तर असाही प्रश्न विचारला की ही समस्या सामान्य क्रमवारीपेक्षा मूलतः अधिक कठीण असू शकेल का, म्हणजे तिला 1 पेक्षा मोठ्या घाताइतका n लागेल का.
आधी भाकीत, दुरुस्ती नंतर
न्यूयॉर्क विद्यापीठातील संजीव खन्ना, हार्वर्ड विद्यापीठातील आरन पटरमन (Aaron Putterman), आणि तसेच न्यूयॉर्क विद्यापीठातील जुनकाई सॉंग (Junkai Song) आता त्या प्रश्नाचे उत्तर देतात: नाही. त्यांचा यादृच्छिक (randomised) अल्गोरिदम कोणत्याही आलेखावर सरासरी सुमारे n log⁴ n तुलनांमध्ये क्रमवारी लावतो — सामान्य क्रमवारीपेक्षा केवळ काही लॉगरिदमीय गुणकांनी अधिक. आणि, ते लिहितात, तो “तुलनेने सोपा” आहे. पण हा लाभ सैद्धांतिक आहे: सिद्धतेतील स्थिरांक प्रचंड आहेत (2³² सारखे गुणक), त्यामुळे हा फायदा केवळ खूप मोठ्या n साठीच दिसतो.
तो एका ज्ञात निकालावर उभा आहे: जर कोणी तुम्हाला प्रत्येक दुव्याच्या दिशेचा एक अंदाज दिला, जो त्यांपैकी w दुव्यांवर चुकीचा आहे, तर सुमारे n log n + w तुलनांमध्ये क्रम परत मिळवता येतो. म्हणून काम असे बनते: कमी तुलना वापरून कमी चुका असलेला अंदाज तयार करणे. कळीच्या पायऱ्या:
- एक ढोबळ पहिला अंदाज. जोडलेल्या जोड्यांच्या एका यादृच्छिक नमुन्याची तुलना करा आणि उत्तरांशी सुसंगत असा कोणताही क्रम निवडा. त्यात अनेक चुका असतात, पण फार जास्त नाहीत.
- चुका दुरुस्त करण्याऐवजी वेगळ्या काढा. चुकीचे अंदाज सुधारण्याऐवजी, अल्गोरिदम आलेखाचे असे भाग शोधतो जिथे चुका सरासरीपेक्षा दाट आहेत, आणि त्यांना बाजूला ठेवतो. प्रत्येक फेरी उरलेल्या चुका, अपेक्षित मूल्याच्या दृष्टीने (in expectation), चार पटीने कमी करते.
- नंतर परत या. बाजूला ठेवलेले दुवे नंतरच्या एका टप्प्यात हाताळले जातात. प्रत्येक टप्पा अजूनही प्रलंबित असलेल्या दुव्यांपैकी किमान अर्धे निकाली काढतो, त्यामुळे एक दशलक्ष दुव्यांसाठी सुमारे वीस टप्पे पुरेसे असतात.
यंत्रांच्या साहाय्याने सापडलेली सिद्धता
या शोधनिबंधातील AI-वापराचे निवेदन असामान्यरीत्या तपशीलवार आहे. त्यात म्हटले आहे की ChatGPT 6-Astra “सुधारित मर्यादा सिद्ध करण्यात अत्यावश्यक होते”. एका मॉडेलने आधी सुमारे n¹·³³ तुलना वापरणारा एक अल्गोरिदम शोधला, आणि मग ते अडले. लेखकांनी तो n¹·² पर्यंत पुढे नेला; मग, अनेक आठवड्यांत डझनावारी वेळा सूचना (prompt) दिल्यानंतर, मॉडेल्सनी लागोपाठ सुधारणा शोधल्या — n^(10/9), n^(17/16), n^(19/18) — आणि अखेर जवळजवळ रेषीय (near-linear) अल्गोरिदम गाठला. लेखक पुढे म्हणतात की त्यांची स्वतःची मधली पायरी त्या अंतिम शोधासाठी अत्यावश्यक होती का, हे स्पष्ट नाही.
अजूनही काय खुले आहे
हा निकाल तुलना मोजतो, गणनकाळ नव्हे: सध्याच्या स्वरूपात, अल्गोरिदम बहुपदी वेळेत (polynomial time) चालत नाही, तर 2011 ची पद्धत चालत होती. लेखक तीन खुले प्रश्न नोंदवतात: उरलेले लॉगरिदमीय गुणक काढून टाकता येतील का, यादृच्छिकतेविना चालणारा अल्गोरिदम तितकीच चांगली कामगिरी करू शकेल का, आणि एखादा कार्यक्षम अल्गोरिदम तुलनांची तीच संख्या गाठू शकेल का — किंवा निदान n¹·⁵ ला तरी मागे टाकू शकेल का.
