घातीय समय परिकल्पना गलत है [pdf]
OpenAI से आए एक नए preprint में दावा किया गया है कि उसने 3-SAT के लिए उपघातीय-समय का एल्गोरिथ्म देकर Exponential Time Hypothesis को खारिज कर दिया है, जो एक प्रमुख NP-complete समस्या है। टिप्पणीकारों का कहना है कि यह एक बड़ा सैद्धांतिक breakthrough है जो एक व्यापक रूप से इस्तेमाल होने वाली hardness assumption को हटाता है और इस विश्वास को (थोड़ा) कमज़ोर करता है कि P≠NP होगा, लेकिन फिर भी यह किसी व्यावहारिक या बहुपद-समय समाधान से बहुत दूर है और अधिकांश NP समस्याओं को संभावित रूप से घातीय ही छोड़ता है। चर्चा का बड़ा हिस्सा इस बात पर केंद्रित है कि समय-सीमा वास्तव में क्या अर्थ रखती है, यह क्यों अपने-आप सभी NP समस्याओं को उपघातीय या cryptography को तोड़ने वाला नहीं बनाती, और कैसे इस तरह के “galactic” algorithms फिर भी इस बारे में हमारी अंतर्दृष्टि बदल सकते हैं कि किस तरह के algorithms संभव हैं।
महत्त्व और P vs NP से संबंध
- कई टिप्पणीकार इसे एक बहुत बड़ा सैद्धांतिक परिणाम मानते हैं, “P vs NP के समान स्तर” का, लेकिन इस बात पर ज़ोर देते हैं कि यह P vs NP को हल नहीं करता।
- ETH के गलत होने से एक व्यापक रूप से इस्तेमाल होने वाली धारणा हट जाती है; ETH/SETH पर निर्भर बहुत-सा पूर्व कार्य फिर से देखना पड़ सकता है।
- कुछ लोग इसे P≠NP में विश्वास को थोड़ा कमज़ोर करने वाला मानते हैं; दूसरों का तर्क है कि इससे ज़्यादा कुछ नहीं बदलता, सिवाय इसके कि “कठिन” समस्याओं के बारे में हमारी अंतर्दृष्टि गलत साबित हुई।
परिणाम वास्तव में क्या दावा करता है
- ETH कहता था कि k‑SAT (आमतौर पर 3‑SAT) के लिए समय ~2^{Ω(n)} आवश्यक है।
- पेपर एक उपघातीय एल्गोरिथ्म देता है, लगभग 2^{n / √log n}, इसलिए ETH गलत है।
- थ्रेड बार-बार एक गलतफ़हमी को सुधारता है: यह NP≠EXP या NP⊊EXP को सिद्ध नहीं करता।
रिडक्शन्स और क्यों NP के लिए उपघातीयता सिद्ध नहीं होती
- एक महत्वपूर्ण सूक्ष्मता: NP समस्याएँ बहुपद समय में SAT में रिड्यूस होती हैं, लेकिन बहुपद रिडक्शन्स instance का आकार बढ़ा सकती हैं।
- 2^{o(n)} जैसे बाउंड्स किसी भी मनमानी बहुपद रिडक्शन के साथ अपने-आप नहीं चलते; इसके लिए 2^{n^{o(1)}} चाहिए होगा।
- इसलिए, 3‑SAT का उपघातीय होना यह नहीं दर्शाता कि सभी NP समस्याएँ उपघातीय हैं।
- यह उन समस्याओं पर अवश्य स्थानांतरित होता है जो SAT तक रैखिक रूप से रिड्यूस होती हैं (जैसे पेपर में सूचीबद्ध कुछ गिनती वाली समस्याएँ)।
ELI5 प्रयास और जटिलता की अंतर्दृष्टि
- कई टिप्पणियाँ SAT, NP, और ETH के लिए सरल व्याख्याएँ देती हैं, और यह ज़ोर देती हैं:
- NP = कुशलता से सत्यापनीय (एक संकेत के साथ), ज़रूरी नहीं कि कुशलता से हल करने योग्य।
- उपघातीय अभी भी खगोलीय रूप से बड़ा हो सकता है; बहुपद और घातीय समय के बीच बहुत बड़ा अंतर है।
व्यावहारिक प्रभाव और “galactic” एल्गोरिद्म
- SAT-solver विशेषज्ञ इन एल्गोरिद्मों को “galactic” कहते हैं: स्थिरांक इतने बड़े हैं कि वास्तविक दुनिया के instance मौजूदा solvers से ही बेहतर हल होते रहते हैं।
- वास्तविक SAT instance अक्सर worst-case से कहीं आसान होते हैं; किसी तात्कालिक प्रदर्शन-लाभ की अपेक्षा नहीं है।
व्यापक निहितार्थ और प्रतिक्रियाएँ
- कुछ लोग इसे अंतर्ज्ञान को थोड़ा इस ओर खिसकाने वाला मानते हैं कि “शायद ऐसे चतुर एल्गोरिद्म मौजूद हैं जिनकी हमने कल्पना नहीं की,” जो इस पुराने विचार से मेल खाता है कि कई समस्याओं के तेज़ एल्गोरिद्म हो सकते हैं।
- दूसरों को चिंता है कि जटिलता सिद्धांत में “efficient” का अर्थ क्या वास्तविक दुनिया की दक्षता से मेल खाता है या नहीं; उनका सुझाव है कि P vs NP व्यावहारिक दक्षता के लिए एक खराब प्रॉक्सी हो सकता है।
- क्रिप्टोग्राफी पर प्रभाव को लेकर जिज्ञासा और अटकलें हैं, लेकिन थ्रेड नोट करता है कि इस परिणाम से कोई मौजूदा cryptosystem स्पष्ट रूप से टूटता नहीं दिखता।