एआइ ने एक्सपोनेंशियल टाइम हाइपोथेसिस को गलत साबित किया: इसका क्या मतलब है

OpenAI और Anthropic ने अलग-अलग प्रकाशित प्रूफ में दिखाया है कि एक्सपोनेंशियल टाइम हाइपोथेसिस गलत है।

ETH सैद्धांतिक कंप्यूटर विज्ञान में 27 साल पुराना एक अनुमेय है, जो कहता है कि कुछ समस्याएँ ब्रूट फोर्स की तुलना में कहीं तेज़ कभी हल नहीं की जा सकतीं। अब, शीर्ष एआइ लैब्स कहती हैं कि यह बात सही नहीं है।

अगर ये प्रूफ टिके रहे, तो ये कंप्यूटर विज्ञान में अब तक का सबसे महत्वपूर्ण एआइ-जनित परिणाम होगा। इससे उन सैकड़ों शोध-पत्रों पर पुनर्विचार करना भी मजबूरन पड़ेगा, जिन्होंने ETH को सही मानकर काम किया था।

इस लेख में, हम समझाएँगे कि एक्सपोनेंशियल टाइम हाइपोथेसिस का मतलब क्या है—साथ ही संबंधित P बनाम NP का भी। हम यह भी देखेंगे कि दोनों लैब्स ने ठीक-ठीक क्या दावा किया है, प्रूफ कैसे जाँचे गए, और क्रिप्टोग्राफी में क्या बदलता है और क्या नहीं।

सरल शब्दों में P बनाम NP

P बनाम NP पूछता है कि क्या हर वह समस्या, जिसका उत्तर जाँचना आसान है, हल करना भी आसान है। यह सात मिलेनियम प्राइज़ समस्याओं में से एक है, और इस खबर के बाद भी अब तक खुली हुई है।

सुडोकू इसकी क्लासिक मिसाल है। भरा हुआ ग्रिड जाँचना सेकंडों का काम है: हर पंक्ति, स्तंभ, और बॉक्स में दोहराव देख लें। लेकिन लगभग खाली ग्रिड से हल ढूँढ़ना कहीं लंबा चल सकता है, और जैसे-जैसे ग्रिड बढ़ता है, यह अंतर उछलता जाता है।

P उन समस्याओं का वर्ग है जिन्हें कंप्यूटर बहुपद समय में हल कर सकता है, यानी इनपुट आकार n बढ़ने पर काम n^², n^³ जैसी दर से बढ़ता है।
NP उन समस्याओं का वर्ग है जिनके प्रस्तावित हल को कंप्यूटर बहुपद समय में सत्यापित कर सकता है।

P की हर समस्या NP में भी है। खुला सवाल यह है कि क्या इसका उलटा सही है। अधिकतर कंप्यूटर वैज्ञानिक मानते हैं कि P ≠ NP, यानी कुछ समस्याएँ जाँचने की तुलना में मूलतः हल करने में कठिन होती हैं। आधुनिक क्रिप्टोग्राफी इसी धारणा पर टिकी है: एन्क्रिप्ट करना आसान है, लेकिन बिना कुंजी के डीक्रिप्ट करना कठिन होना चाहिए।

एक्सपोनेंशियल टाइम हाइपोथेसिस क्या है?

ETH और सटीक है: यह दावा करता है कि एक विशिष्ट NP समस्या, 3-SAT, किसी भी चतुर एल्गोरिद्म के बावजूद एक्सपोनेंशियल समय मांगती है। UC सैन डिएगो के रसेल इंपालियाज़ो और रामामोहन पाटुरी ने इसे 1990 के दशक के अंत में प्रस्तावित किया था, और फ्रांसिस ज़ेन ने आधारभूत कार्य में योगदान दिया था।

3-SAT समस्या

3-SAT में, आपको n सत्य/असत्य चर और क्लॉज़ों की सूची से बना एक सूत्र मिलता है। हर क्लॉज़ तीन स्थितियों को OR से जोड़ता है, जैसे "x₁ सत्य है या x₄ असत्य है या x₇ सत्य है।" काम यह है कि चरों को ऐसे मान दें कि हर क्लॉज़ एक साथ संतुष्ट हो जाए।

ब्रूट फोर्स सभी 2ⁿ संयोजनों को आजमाता है, इसलिए हर अतिरिक्त चर काम को दोगुना कर देता है। आप समझ सकते हैं कि लगभग 100 चरों के आसपास यह निराशाजनक हो जाता है।

ETH क्या कहता है

ETH कहता है कि कोई स्थिरांक c > 1 मौजूद है, जिसके लिए 3-SAT को cⁿ से तेज़ कोई एल्गोरिद्म हल नहीं कर सकता। चतुर एल्गोरिद्म बेस को 2 से नीचे ला सकते हैं, लेकिन सबएक्सपोनेंशियल तक कभी नहीं। औपचारिक रूप से: कोई δ > 0 मौजूद है ताकि 3-SAT समय O(2^δn) में हल नहीं हो सकता।

दशकों तक प्रगति इसी तस्वीर से मेल खाती रही। शोधकर्ता बेस को धीरे-धीरे घटाते रहे, लेकिन वह 1 से काफी ऊपर रहा। क्योंकि 3-SAT को कई अन्य समस्याओं में बदला जा सकता है, ETH एक कामचलाऊ परिकल्पना बन गया। शोधकर्ताओं ने इसका उपयोग यह तर्क देने में किया कि Clique, Vertex Cover, Independent Set जैसी समस्याएँ भी बहुत तेज़ी से हल नहीं हो सकतीं।

नए परिणाम की तुलना

दृष्टिकोण	3-SAT के लिए रनिंग टाइम	घातीय रूप से बढ़ता है?
ब्रूट फोर्स	2ⁿ	हाँ
अक्टूबर 2026 से पहले सर्वश्रेष्ठ (निश्चित)	लगभग 1.328ⁿ	हाँ
अक्टूबर 2026 से पहले सर्वश्रेष्ठ (रैंडमाइज़्ड)	लगभग 1.308ⁿ	हाँ
OpenAI और Anthropic (अक्टूबर 2026)	2^O(n log log n / √log n)	नहीं: सबएक्सपोनेंशियल

नया बाउंड शॉर्टहैंड में 2^o(n) लिखा जाता है। जोड़ा गया हर चर प्रति लागत n बढ़ने पर 1 की ओर सिमटती जाती है—ठीक वही जिसे ETH असंभव कहता था।

OpenAI और Anthropic ने क्या घोषित किया

दोनों लैब्स स्वतंत्र रूप से लगभग समान सबएक्सपोनेंशियल बाउंड पर पहुँचीं, और दोनों ने अपने पेपर्स को Lean प्रूफ असिस्टेंट में मशीन-चेक्ड प्रूफ से समर्थित किया।

	OpenAI	Anthropic
पेपर	"The Exponential Time Hypothesis Is False" (67 पृष्ठ)	"A 2^o(n) Time Algorithm for 3-SAT" (49 पृष्ठ)
मॉडल	अनाम आंतरिक मॉडल	आंतरिक Claude रिसर्च मॉडल, लेखक के रूप में श्रेय
मुख्य विचार मिला	16 अक्टूबर, 2026	16 अक्टूबर, 2026
सार्वजनिक किया	26 अक्टूबर, 2026	26–27 अक्टूबर, 2026
सत्यापन	Lean प्रूफ एक थोड़े कमजोर बाउंड का, जो ETH को फिर भी खारिज करता है	Mathlib के विरुद्ध Lean 4 प्रूफ, दूसरे कर्नेल से पुनः जाँचा गया
अतिरिक्त दावे	स्पीडअप पूरे NP पर लागू नहीं होता	मजबूत ETH (SETH) को भी खारिज; नया सर्किट लोअर बाउंड

Anthropic कहता है कि Claude ने लगभग 1.4 करोड़ टोकनों का आउटपुट बनाने के बाद बिना किसी मानव इनपुट के मुख्य एल्गोरिद्म ढूँढ़ लिया। इसकी विधि टेन्सर नेटवर्क्स और रैंक तर्कों का उपयोग करती है। उसके बाद शोधकर्ताओं ने अंतिम पेपर में मदद की।

दोनों लैब्स को वही चीज़ एक ही दिन कैसे मिली?

किसी लैब ने टाइमिंग नहीं समझाई है। Anthropic के पेपर में दोनों परिणामों को स्वतंत्र और समकालिक कहा गया है, और दोनों लिखतें गणित में अलग राहें लेते हुए लगभग एक ही बाउंड तक पहुँचती हैं।

कुछ संदर्भ इस ओवरलैप को पहली नजर से कम चौंकाने वाला बनाते हैं। दोनों लैब्स अपने मॉडलों को खुले समस्याओं की लंबी सूचियों पर आजमा रही थीं, और सिर्फ OpenAI ने ही अक्टूबर की शुरुआत में सैकड़ों एआइ-जनित गणित पांडुलिपियाँ जारी कीं। ETH इस क्षेत्र के सबसे प्रसिद्ध लक्ष्यों में से एक है, और दोनों मॉडलों ने एक ही प्रकाशित शोध से सीखा। विज्ञान में स्वतंत्र, एक-साथ खोज भी पुराना पैटर्न है—जैसे कलन पर न्यूटन और लीबनिज़, या प्राकृतिक चयन पर डार्विन और वालेस।

प्रूफ कितने ठोस हैं?

Lean यह पुष्ट करता है कि कोई औपचारिक कथन उसके स्वीकृत स्वयंसिद्धों से तार्किक रूप से निकलता है। यह यह पुष्ट नहीं कर सकता कि औपचारिक कथन कागज़ वाले कथन के समान है। Anthropic नोट करता है कि इस मेल को कोई मशीन नहीं जाँचती, और OpenAI कहता है कि उसका Lean फ़ाइल उसके हेडलाइन से थोड़ा कमजोर बाउंड साबित करती है।

अब, वही शोधकर्ता जिन्होंने समस्या प्रस्तावित की थी—इंपालियाज़ो और पाटुरी—MIT के रयान विलियम्स के साथ मिलकर यह आकलन करने के लिए कार्यशालाएँ आयोजित कर रहे हैं कि क्या औपचारिक कथन सच में ETH को पकड़ते हैं। उनके पत्र में बल दिया गया है कि समीक्षा में भाग लेना अनुमोदन नहीं है। इस लेखन तक, किसी ने सार्वजनिक रूप से खामी नहीं बताई थी।

विलियम्स ने कहा है कि OpenAI के प्रूफ के कुछ हिस्से नियमित दिखते हैं, जबकि "दो या तीन एलियन-से दिखने वाले हिस्से" अब भी जांच के लायक हैं। ETH के लेखकों में से एक इंपालियाज़ो ने परिणाम को अत्यंत चौंकाने वाला बताया है।

क्या बदलता है और क्या नहीं

व्यवहार में, आज लगभग कुछ नहीं बदलता (उफ़): नए एल्गोरिद्म केवल उन इनपुट्स पर ब्रूट फोर्स से बेहतर हैं जो किसी भी कंप्यूटर की क्षमता से कोसों बड़े हैं।

तेज़ SAT सॉल्वर नहीं

Anthropic के पेपर के अनुसार, इसकी विधि केवल खगोलीय रूप से बड़े इनपुट्स पर ब्रूट फोर्स से आगे निकलती है। सामान्य तौर पर प्रति चर पाँच क्लॉज़ वाले सूत्रों के लिए, क्रॉसओवर बिंदु लगभग 10,000 अंकों वाली संख्या है। सबसे सामान्य स्थिति में, यह लगभग 10 करोड़ अंकों वाली संख्या है।

लेखक यह भी कहते हैं कि उनकी पद्धति लगभग 1 करोड़ चरों से कम पर किसी चीज़ में मददगार होने की संभावना नहीं है। चिप वेरिफिकेशन, शेड्यूलिंग, और प्लानिंग में उपयोग होने वाले SAT सॉल्वर इससे तेज़ नहीं होंगे।

क्रिप्टोग्राफी टूटी नहीं है

यह परिणाम P बनाम NP को नहीं छूता। कोई ऐसा दिखावा नहीं कर रहा। OpenAI कहता है कि उसने जाँचा कि क्या एल्गोरिद्म वास्तविक क्रिप्टोसिस्टम्स को तोड़ता है, और उसे काफ़ी भरोसा है कि ऐसा नहीं है।

सिद्धांत फिर से लिखा जाएगा

बड़ा असर शोध पर है। ETH या SETH पर टिके कड़ेपन के परिणाम अब नए आधार माँगते हैं, और कुछ शोधकर्ताओं ने कहा है कि उनके वर्षों के काम की समीक्षा करनी पड़ सकती है। हालांकि सबकुछ नहीं ढहता। Anthropic नोट करता है कि यह परिणाम ऑर्थोगोनल वेक्टर समस्या को खारिज नहीं करता, जो कई फाइन-ग्रेन्ड कॉम्प्लेक्सिटी परिणामों का सहारा है।

एआइ के लिए इसका महत्व

सुर्खी 3-SAT से कम और उत्तर किसने पाया इससे ज़्यादा है: दो एआइ प्रणालियों ने स्वतंत्र रूप से एक ऐसे अनुमेय को पलट दिया जिस पर विशेषज्ञ पीढ़ी भर से भरोसा करते थे।

शोध सहयोगी के रूप में एआइ

शोधकर्ता अब बताते हैं कि हर सप्ताह-दो सप्ताह में नए एआइ परिणाम आते हैं, चल रही परियोजनाओं को बीच में बाधित करते हुए। Lean जैसे औपचारिक टूल केंद्रीय बन रहे हैं, क्योंकि वे मनुष्यों को लंबी मशीन-लिखित प्रूफ पर भरोसा करने देते हैं, बिना हर पंक्ति फिर से निकाले।

छिपे शॉर्टकट और स्व-सुधार

ETH इस विश्वास को पकड़े हुए था कि कुछ सर्च समस्याओं में कोई चतुर शॉर्टकट नहीं होता। अगर यह विश्वास गलत है, तो अन्य स्पष्ट रूप से कठिन समस्याओं में भी शॉर्टकट छिपे हो सकते हैं।

मैं एल्गोरिद्म खोज को एक ऐसे क्षेत्र के रूप में देख रहा हूँ जहाँ ऐसे शॉर्टकट रिकर्सिव सेल्फ-इम्प्रूवमेंट के लिए बहुत मायने रख सकते हैं—यानी ऐसे एआइ सिस्टम जो बेहतर एआइ डिजाइन करने में मदद करते हैं। तेज़ एल्गोरिद्म खोजने के लिए एआइ का उपयोग करना उसका एक ठोस रास्ता है, भले ही इस परिणाम से आज सीधे ऐसा कुछ न होता हो।

डेटा प्रैक्टिशनर्स के लिए अर्थ

डेटा के साथ काम करने वालों के लिए तीन सीखें उभरती हैं:

कॉम्प्लेक्सिटी थ्योरी केवल अकादमिक नहीं है: जानना कि कोई समस्या NP-कठिन है, बताता है कि कब अनुमानी विधियाँ, अनुमान, या सॉल्वर के बारे में सोचना चाहिए, न कि सटीक खोज के।
वेरिफिकेशन एक कौशल है: जैसे-जैसे एआइ अधिक कोड और विश्लेषण जनरेट करता है, उसके आउटपुट की जाँच (टेस्ट, प्रूफ, या पुनरुत्पाद्य पाइपलाइनों से) उतनी ही महत्वपूर्ण है जितना कि उसे पैदा करना।
असिम्प्टोटिक्स गुमराह कर सकते हैं: सिद्धांत में "तेज़" एल्गोरिद्म वास्तविक आकारों पर बेकार हो सकता है।

निष्कर्ष

अगर प्रूफ विशेषज्ञ समीक्षा में खरे उतरे, तो एक्सपोनेंशियल टाइम हाइपोथेसिस उन व्यापक रूप से मानी गई धारणाओं की छोटी सूची में शामिल हो जाएगा जो गलत निकलीं (जैसे ऑयलर का सम ऑफ पावर्स अनुमेय)। लेकिन P बनाम NP अब भी खुला है और फिलहाल क्रिप्टोग्राफी सुरक्षित है।

अगले मील के पत्थर होंगे—ETH के मूल लेखकों द्वारा संचालित समीक्षा कार्यशालाएँ, एल्गोरिद्म की स्वतंत्र पुनः-इम्प्लीमेंटेशन, और क्या कोई बाउंड को और कसा पाता है।

ऐसी कहानियों की बुनियाद समझने के लिए हमारे डेटा स्ट्रक्चर और एल्गोरिद्म, Python प्रोग्रामिंग, और मशीन लर्निंग पर पाठ्यक्रम देखें। ये Big-O सोच को कवर करते हैं, जो ऐसे परिणामों को पढ़ने लायक बनाती है।

लेखक

Josef Waples

मैं एक डेटा साइंस संपादक हूँ और वैज्ञानिक पत्रिकाओं में प्रकाशित शोध लेखों में योगदान दे चुका/चुकी हूँ। मुझे विशेष रूप से रैखिक बीजगणित, सांख्यिकी, R, और इसी तरह के विषयों में रुचि है।

FAQs

क्या एआइ ने अभी साबित कर दिया कि P = NP?

नहीं। यह परिणाम एक्सपोनेंशियल टाइम हाइपोथेसिस (ETH) को, जो 3-SAT की कठिनाई पर एक मजबूत मान्यता है, खारिज करता है। P बनाम NP अब भी अनसुलझा है, हालाँकि कुछ विशेषज्ञ अब P = NP को पहले से थोड़ा अधिक वज़न दे रहे हैं।

क्या अब एन्क्रिप्शन असुरक्षित है?

नहीं। OpenAI कहता है कि उसने जाँच की है और उसे पर्याप्त भरोसा है कि एल्गोरिद्म वास्तविक क्रिप्टोसिस्टम्स को नहीं तोड़ता। एलिप्टिक कर्व्स पर फ़ॉलो-अप अटैक आज उपयोग में आने वाली कर्व्स के विरुद्ध कोई बढ़त नहीं देता।

क्या SAT सॉल्वर या ऑप्टिमाइज़ेशन टूल्स तेज़ हो जाएँगे?

इस परिणाम से नहीं। नए एल्गोरिद्म केवल उन इनपुट्स पर ब्रूट फोर्स से बेहतर हैं जिनमें खगोलीय संख्या में चर हों—किसी भी वास्तविक समस्या से बहुत परे।

क्या प्रूफ का सत्यापन हो चुका है?

आंशिक रूप से। दोनों प्रूफ Lean प्रूफ असिस्टेंट में जाँचे गए हैं, लेकिन मनुष्यों को अब भी यह पुष्ट करना है कि औपचारिक कथन ETH से मेल खाते हैं। ETH के मूल लेखकों द्वारा संचालित कार्यशालाएँ अभी इसकी समीक्षा कर रही हैं।

OpenAI और Anthropic को एक ही दिन यह कैसे मिला?

दोनों कहते हैं कि उनके मॉडलों ने 16 अक्टूबर, 2026 को मुख्य विचार पाया, और दोनों इसे स्वतंत्र काम बताते हैं। इसके आगे टाइमिंग की कोई व्याख्या नहीं दी गई।

विषय

कृत्रिम बुद्धिमत्ता