संगणन आणि एआयप्रीप्रिंटसिद्धांतवाचनासाठी ३ मिनिटे

क्लीक शोधण्याची वेगमर्यादा 40 वर्षांनंतर कोसळली

n लोकांच्या एका सामाजिक जाळ्याची कल्पना करा. त्यांच्यापैकी असा k जणांचा एखादा गट आहे का, ज्यातील सर्वजण एकमेकांना ओळखतात? संगणकशास्त्रज्ञ अशा गटाला k-क्लीक (k-clique) म्हणतात, आणि तो शोधणे ही असंख्य उपयोग असलेली एक अभिजात समस्या आहे. भोळा मार्ग k लोकांचा प्रत्येक शक्य गट तपासतो, असे साधारण n^k गट — मोठ्या जाळ्यांसाठी निरुपयोगी.

1985 ची एक युक्ती आणि एक दीर्घ आव्हान

40 हून अधिक वर्षांपूर्वी, यारोस्लाव नेशेत्रिल (Jaroslav Nešetřil) आणि स्वातोप्लुक पोल्याक (Svatopluk Poljak) यांना एक लघुमार्ग सापडला. त्यांनी k-क्लीकचा शोध एका मोठ्या आलेखातील (graph) त्रिकोणाच्या शोधात बदलला, जो पुढे आव्यूहांच्या गुणाकाराने (matrix multiplication), म्हणजे संख्यांच्या मोठ्या तक्त्यांच्या गुणाकाराने, करता येतो. खर्च ω वर अवलंबून असतो, जो आव्यूह-गुणाकाराचा घातांक आहे: त्यांच्या पद्धतीला सुमारे n^(ωk/3) पायऱ्या लागतात. ω नेमका किती आहे हे कोणालाही माहीत नाही. तो किमान 2 आहे, आणि लेख 9/4 ही एक अलीकडील वरची मर्यादा उद्धृत करतो.

1985 च्या त्या पद्धतीच्या घातांकावर कधीच मात झाली नाही. 2004 मध्ये, गेरहार्ड वोगिंगर (Gerhard Woeginger) यांनी संशोधकांना एखाद्या निश्चित k साठी यापेक्षा चांगले करून दाखवण्याचे आव्हान दिले; दोन दशकांहून अधिक काळ लोटला. दरम्यान k-क्लीक परिकल्पना (k-Clique Hypothesis) — n^(ωk/3) हेच मूलतः सर्वोत्तम शक्य आहे ही — “सूक्ष्म-स्तरीय जटिलता” (fine-grained complexity) या क्षेत्राचा पाया बनली. संशोधकांनी तिचा वापर करून असा युक्तिवाद केला की व्याकरणांच्या विश्लेषणापासून (parsing grammars) संकुचित माहितीच्या विश्लेषणापर्यंत, इतर अनेक समस्याही अधिक वेगाने सोडवता येणार नाहीत.

सरकणारे लक्ष्य

ही परिकल्पना खोडून काढण्यात एक विशेष अडचण होती. तिचा अपेक्षित खर्च ω वर अवलंबून आहे, जो अज्ञात आहे. ω च्या आजच्या सर्वोत्तम मूल्यावर मात करणारा एखादा अल्गोरिदम, पुढे कोणाला अधिक वेगवान आव्यूह-गुणाकार सापडला तर, परिकल्पनेवर मात करणे थांबवू शकतो.

MIT मधील व्हर्जिनिया व्हॅसिलेव्स्का विल्यम्स (Virginia Vassilevska Williams) आणि Tel Aviv University मधील ओर झमीर (Or Zamir) ही अडचण टाळतात. त्यांनी सिद्ध केले आहे की पुरेशा मोठ्या प्रत्येक k साठी, k-क्लीक सुमारे n^((ω/3 − c)k) पायऱ्यांत शोधता येतो — आणि मोजताही येतो —, जिथे c हा k वर किंवा ω वर अवलंबून नसलेला एक धन स्थिरांक आहे. ही बचत ω च्या खऱ्या मूल्याच्या तुलनेत मोजली जाते, ते काहीही निघो. ω = 2 असले, म्हणजे कल्पना करता येणारी सर्वोत्तम स्थिती, तरीही ती टिकते.

पाचर दुमडणे

पद्धतीचा गाभा नऊ शिरोबिंदूंच्या आकृतिबंधांशी (patterns) संबंधित आहे. प्रमाणित पद्धत त्यांना तीन-तीनच्या तीन गटांत विभागते आणि तीन प्रचंड आव्यूहांचा गुणाकार करते. लेखक एका पाचरीकडे (wedge) पाहतात — एक शिरोबिंदू सामायिक करणाऱ्या दोन कडा — आणि दोन आव्यूहांच्या दरम्यान काहीही न बदलणारा एक तक्ता घालतात: एकक आव्यूह (identity). मग ते त्या एकक आव्यूहाला काही “अदलाबदली” (swaps) आणि कमी कोटीचा (low rank) एक उरलेला भाग यांची बेरीज म्हणून लिहितात; प्रत्येक अदलाबदल पाचरीच्या दोन कडा एकात विलीन करते.

अदलाबदलींमधून कमी कडा असलेले अधिक साधे आकृतिबंध मिळतात, जे पुन्हा त्याच पद्धतीने हाताळले जातात; नऊ शिरोबिंदूंच्या आकृतिबंधात जास्तीत जास्त 36 कडा असतात, त्यामुळे पुनरावर्तन (recursion) संपते. कमी कोटीचा उरलेला भाग गुणाकार करायच्या आव्यूहांना लहान करतो. ही युक्ती एकाच वेळी दोन वेगवेगळ्या पाचरींवर लागू केल्यामुळेच ω = 2 असतानाही फायदा टिकून राहतो. मग नऊच्या पटीत असलेला कोणताही k नऊ खंडांमध्ये गटबद्ध करता येतो.

खरा, पण अगदी लहान

लेखक फायद्यासाठी आकडे देत नाहीत. ते स्थिरांकांचे वर्णन “इष्टतमीकरणाविना अत्यल्प ते लक्षणीय इष्टतमीकरणांसह अगदी लहान यांच्या दरम्यान” असे करतात. मुद्दा प्रत्यक्ष वापरातील वेगाचा नाही: दशकानुदशके ज्यावर विश्वास ठेवला गेला तो अडथळा अस्तित्वातच नाही, हा आहे.

परिणाम क्लीकच्याही पलीकडे पोहोचतात. Max-Cut आणि Max-2-SAT सारख्या कठीण इष्टतमीकरण समस्यांसाठीच्या अचूक अल्गोरिदमना, ज्यांना n चलांसाठी सुमारे 2^(ωn/3) पायऱ्या लागत, आता एक लहान घातांक मिळतो. कोणत्याही निश्चित लहान आलेखाच्या प्रती मोजण्यालाही तो मिळतो.

AI ने काय केले

एका स्वतंत्र विभागात, लेखक त्यांनी ChatGPT-6 सोबत कसे काम केले याचे वर्णन करतात; ते त्याच्या सार्वजनिक वेब इंटरफेसद्वारे वापरले गेले. पाच व्यक्तींच्या क्लीकसाठी त्यांच्या स्वतःच्या कल्पनांपासून आणि दुसरे एक अनुमान, घातांकी काल परिकल्पना (Exponential Time Hypothesis), खोडून काढणाऱ्या OpenAI च्या एका अलीकडील निकालापासून सुरुवात करून, मॉडेलने 5-क्लीकसाठी एक पहिली, गुंतागुंतीची सुधारणा शोधली. मग लेखकांनी, AI च्या मदतीने, ती गाळून सिद्धतेच्या गाभ्यातील बैजिक विघटनात (algebraic decomposition) रूपांतरित केली, जिला ते “जवळजवळ-पूर्णपणे AI चे योगदान” मानतात. तिच्याभोवती उभारलेली अल्गोरिदमिक चौकट, ते म्हणतात, मुख्यतः त्यांची आहे.

एक टिप्पणी ठळकपणे लक्षात राहते. AI ने निर्माण केलेल्या दुर्बोध सिद्धता माणसांना वाचायला कठीण असतात, असे लेखक नमूद करतात — आणि “त्या AI ला स्वतःलाही समजायला कठीण आहेत हे पाहून ते प्रभावित झाले”.