क्लीक खोजने की गति-सीमा 40 वर्षों बाद टूटी
n लोगों वाले एक सोशल नेटवर्क की कल्पना कीजिए। क्या उनमें k लोगों का कोई ऐसा समूह है जिसमें सब एक-दूसरे को जानते हों? कंप्यूटर वैज्ञानिक ऐसे समूह को k-क्लीक (k-clique) कहते हैं, और उसे खोजना अनगिनत उपयोगों वाली एक क्लासिक समस्या है। सीधा-सादा तरीक़ा k लोगों के हर संभव समूह की जाँच करता है, जो मोटे तौर पर n^k होते हैं — बड़े नेटवर्कों के लिए निराशाजनक।
1985 की एक युक्ति और एक लंबी चुनौती
40 से ज़्यादा वर्ष पहले, यारोस्लाव नेशेत्रिल (Jaroslav Nešetřil) और स्वातोप्लुक पोल्याक (Svatopluk Poljak) ने एक शॉर्टकट खोजा। उन्होंने k-क्लीक की खोज को एक बड़े ग्राफ़ में त्रिभुज की खोज में बदल दिया, जो बदले में आव्यूहों के गुणन (multiplying matrices) से किया जा सकता है, यानी संख्याओं की बड़ी तालिकाओं के गुणन से। लागत ω पर निर्भर करती है, जो आव्यूह गुणन का घातांक (exponent) है: उनका तरीक़ा लगभग n^(ωk/3) चरण लेता है। ω का सटीक मान कोई नहीं जानता। यह कम से कम 2 है, और लेख 9/4 की एक हालिया ऊपरी सीमा का हवाला देता है।
1985 के उस तरीक़े के घातांक को कभी मात नहीं दी गई। 2004 में, गेरहार्ड वोगिंगर (Gerhard Woeginger) ने शोधकर्ताओं को किसी नियत k के लिए इससे बेहतर करने की चुनौती दी; दो दशक से ज़्यादा बीत गए। इस बीच k-क्लीक परिकल्पना (k-Clique Hypothesis) — कि n^(ωk/3) अनिवार्य रूप से सबसे अच्छा संभव है — “सूक्ष्म-स्तरीय जटिलता” (fine-grained complexity) की एक नींव बन गई। शोधकर्ताओं ने इसका उपयोग यह तर्क देने के लिए किया कि व्याकरणों के पार्सिंग (parsing) से लेकर संपीड़ित डेटा के विश्लेषण तक, कई अन्य समस्याएँ भी इससे तेज़ी से हल नहीं की जा सकतीं।
एक खिसकता हुआ लक्ष्य
इस परिकल्पना का खंडन करने में एक ख़ास कठिनाई थी। इसकी अनुमानित लागत ω पर निर्भर करती है, जो अज्ञात है। ω के आज के सबसे अच्छे मान को मात देने वाला कोई एल्गोरिदम परिकल्पना को मात देना बंद कर सकता है, अगर बाद में कोई ज़्यादा तेज़ आव्यूह गुणन खोज ले।
वर्जीनिया वासिलेव्स्का विलियम्स (Virginia Vassilevska Williams, MIT) और ओर ज़मीर (Or Zamir, तेल अवीव विश्वविद्यालय) इस समस्या से बचकर निकलते हैं। वे सिद्ध करते हैं कि हर पर्याप्त बड़े k के लिए, एक k-क्लीक को लगभग n^((ω/3 − c)k) चरणों में खोजा — और गिना भी — जा सकता है, जहाँ c एक धनात्मक स्थिरांक है जो न k पर निर्भर करता है न ω पर। बचत ω के वास्तविक मान के सापेक्ष मापी जाती है, वह जो भी निकले। यह तब भी बनी रहती है जब ω = 2 हो, जो सबसे अच्छी कल्पनीय स्थिति है।
एक फन्नी को मोड़ना
तरीक़े का मूल नौ शीर्षों (vertices) वाले पैटर्नों से जुड़ा है। मानक तरीक़ा उन्हें तीन-तीन के तीन समूहों में बाँटता है और तीन विशाल आव्यूहों का गुणन करता है। लेखक एक फन्नी (wedge) को देखते हैं — एक शीर्ष साझा करने वाले दो किनारे (edges) — और दो आव्यूहों के बीच एक ऐसी तालिका डालते हैं जो कुछ नहीं बदलती: तत्समक (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 के लिए भी कठिन है”।
