जटिलता सिद्धांत की ज्ञान की सीमा तक 50 साल की यात्रा | क्वांटा पत्रिका

2007 में फ़ॉल सेमेस्टर के पहले सप्ताह में, मार्को कार्मोसिनो मैसाचुसेट्स विश्वविद्यालय, एमहर्स्ट में सभी कंप्यूटर विज्ञान की बड़ी कंपनियों के लिए आवश्यक गणित की कक्षा में चले गए। कार्मोसिनो, जो द्वितीय वर्ष का छात्र था, वीडियो गेम डिज़ाइन करने के लिए कॉलेज छोड़ने पर विचार कर रहा था। तब प्रोफेसर ने एक सरल प्रश्न पूछा जो उनके जीवन की दिशा बदल देगा: आप कैसे जानते हैं कि गणित वास्तव में काम करता है?

"उसने मुझे उठकर बैठने और ध्यान देने के लिए प्रेरित किया," याद किया कार्मोसिनो, अब आईबीएम में एक सैद्धांतिक कंप्यूटर वैज्ञानिक हैं। उन्होंने कर्ट गोडेल के काम पर एक वैकल्पिक सेमिनार के लिए साइन अप किया, जिनके चक्करदार आत्म-संदर्भित तर्कों ने पहली बार गणितीय तर्क की सीमाओं को उजागर किया और गणना की मूलभूत सीमाओं पर भविष्य के सभी कार्यों की नींव तैयार की। इसमें लेने के लिए बहुत कुछ था।

कार्मोसिनो ने कहा, "मैं 100% समझ नहीं पाया।" "लेकिन मुझे पता था कि मैं ऐसा करना चाहता था।"

आज, जब अनुभवी शोधकर्ता भी सैद्धांतिक कंप्यूटर विज्ञान में केंद्रीय खुले प्रश्न का सामना करते हैं, जिसे पी बनाम एनपी समस्या के रूप में जाना जाता है, तो उन्हें समझ की कमी महसूस होती है। संक्षेप में, यह प्रश्न पूछता है कि क्या कई कम्प्यूटेशनल समस्याएं जिन्हें लंबे समय से बेहद कठिन माना जाता है, वास्तव में आसानी से हल की जा सकती हैं (एक गुप्त शॉर्टकट के माध्यम से जिसे हमने अभी तक नहीं खोजा है), या क्या, जैसा कि अधिकांश शोधकर्ताओं को संदेह है, वे वास्तव में कठिन हैं। जो जानने योग्य है उसकी प्रकृति से कम कुछ भी दांव पर नहीं है।

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

“कोई रोडमैप नहीं है,” कहा माइकल सिप्सरमैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी के एक अनुभवी जटिलता सिद्धांतकार, जिन्होंने 1980 के दशक में इस समस्या से जूझते हुए कई साल बिताए। "यह ऐसा है जैसे आप जंगल में जा रहे हैं।"

ऐसा लगता है कि यह साबित करना कि कम्प्यूटेशनल समस्याओं को हल करना कठिन है, अपने आप में एक कठिन काम है। लेकिन यह इतना कठिन क्यों है? और यह कितना कठिन है? मेटा-कॉम्प्लेक्सिटी के उपक्षेत्र में कार्मोसिनो और अन्य शोधकर्ता इस तरह के प्रश्नों को कम्प्यूटेशनल समस्याओं के रूप में सुधारते हैं, जटिलता सिद्धांत के लेंस को वापस अपनी ओर मोड़कर क्षेत्र को आगे बढ़ाते हैं।

"आप सोच सकते हैं, 'ठीक है, यह बहुत अच्छा है। हो सकता है कि जटिलता सिद्धांतकार पागल हो गए हों,'' ने कहा राहुल इलंगो, एमआईटी में एक स्नातक छात्र जिसने क्षेत्र में हाल के कुछ सबसे रोमांचक परिणाम दिए हैं।

इन अंतर्मुखी प्रश्नों का अध्ययन करके, शोधकर्ताओं ने सीखा है कि कम्प्यूटेशनल कठोरता साबित करने की कठोरता मौलिक प्रश्नों से गहराई से जुड़ी हुई है जो पहले असंबंधित लग सकती है। स्पष्ट रूप से यादृच्छिक डेटा में छिपे हुए पैटर्न को पहचानना कितना कठिन है? और यदि वास्तव में कठिन समस्याएँ मौजूद हैं, तो वे कितनी बार कठिन होती हैं?

"यह स्पष्ट हो गया है कि मेटा-जटिलता चीजों के दिल के करीब है," ने कहा स्कॉट आरोनसनटेक्सस विश्वविद्यालय, ऑस्टिन में एक जटिलता सिद्धांतकार।

यह उस लंबे और घुमावदार रास्ते की कहानी है जिसने शोधकर्ताओं को पी बनाम एनपी समस्या से मेटा-जटिलता तक पहुंचाया। यह एक आसान यात्रा नहीं रही है - रास्ता झूठे मोड़ों और बाधाओं से भरा हुआ है, और यह बार-बार अपनी ओर मुड़ता है। फिर भी मेटा-कॉम्प्लेक्सिटी शोधकर्ताओं के लिए, एक अज्ञात परिदृश्य में वह यात्रा अपना ही प्रतिफल है। उन्होंने कहा, सरल प्रतीत होने वाले प्रश्न पूछना शुरू करें वैलेंटाइन कबानेट्स, कनाडा में साइमन फ़्रेज़र विश्वविद्यालय में एक जटिलता सिद्धांतकार, और "आपको पता नहीं है कि आप कहाँ जाने वाले हैं।"

ज्ञात अज्ञात

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

ये रिश्ते गणना के बारे में अपरिवर्तनीय सच्चाइयों को दर्शाते हैं जो किसी भी विशिष्ट तकनीक से कहीं आगे जाते हैं। काबनेट्स ने कहा, "यह ब्रह्मांड के नियमों की खोज करने जैसा है।"

"पी" और "एनपी" ए के दो सबसे प्रसिद्ध सदस्य हैं बढ़ती चिड़ियाघर सैकड़ों जटिलता वर्गों में से। मोटे तौर पर कहें तो, P समस्याओं का वह वर्ग है जिसे आसानी से हल किया जा सकता है, जैसे किसी सूची को वर्णानुक्रम में लगाना। एनपी सुडोकू पहेलियों की तरह आसानी से जांचने योग्य समाधान वाली समस्याओं का वर्ग है। चूँकि आसानी से हल होने वाली सभी समस्याओं की जाँच करना भी आसान है, P में समस्याएँ NP में भी हैं। लेकिन कुछ एनपी समस्याओं को हल करना कठिन लगता है - आप कई संभावनाओं को आज़माए बिना तुरंत सुडोकू पहेली का समाधान नहीं ढूंढ सकते। क्या ऐसा हो सकता है कि यह स्पष्ट कठोरता सिर्फ एक भ्रम है - कि हर आसानी से जाँचने योग्य समस्या को हल करने के लिए एक ही सरल तरकीब है?

यदि ऐसा है, तो पी = एनपी: दोनों वर्ग समतुल्य हैं। यदि ऐसा मामला है, तो कुछ एल्गोरिदम होना चाहिए जो विशाल सुडोकू पहेली को हल करना, वैश्विक शिपिंग मार्गों को अनुकूलित करना, अत्याधुनिक एन्क्रिप्शन को तोड़ना और गणितीय प्रमेयों के प्रमाणों को स्वचालित करना आसान बनाता है। यदि पी ≠ एनपी, तो सिद्धांत रूप में हल करने योग्य कई कम्प्यूटेशनल समस्याएं व्यवहार में हमेशा के लिए हमारी समझ से परे रहेंगी।

पी बनाम एनपी समस्या के पहली बार स्पष्ट होने से बहुत पहले ही शोधकर्ता औपचारिक गणितीय तर्क की सीमाओं के बारे में चिंतित थे - वास्तव में, आधुनिक कंप्यूटर विज्ञान की शुरुआत से बहुत पहले। 1921 में, उसी प्रश्न से जूझते हुए जिसने लगभग एक सदी बाद कार्मोसिनो का ध्यान खींचा, गणितज्ञ डेविड हिल्बर्ट ने गणित को पूर्ण निश्चितता के आधार पर स्थापित करने के लिए एक शोध कार्यक्रम का प्रस्ताव रखा। उन्हें आशा थी कि वे कुछ सरल धारणाओं से शुरुआत करेंगे, जिन्हें स्वयंसिद्ध कहा जाता है, और एक एकीकृत गणितीय सिद्धांत प्राप्त किया जाएगा जो तीन प्रमुख मानदंडों को पूरा करता हो।

हिल्बर्ट की पहली शर्त, स्थिरता, आवश्यक आवश्यकता थी कि गणित विरोधाभासों से मुक्त हो: यदि दो विरोधाभासी कथनों को एक ही सिद्धांतों से शुरू करके सिद्ध किया जा सकता है, तो पूरा सिद्धांत अप्राप्य होगा। लेकिन एक सिद्धांत विरोधाभास से मुक्त हो सकता है और फिर भी इसकी पहुंच सीमित हो सकती है। वह हिल्बर्ट की दूसरी शर्त, पूर्णता के लिए प्रेरणा थी: यह आवश्यकता कि सभी गणितीय कथन या तो सिद्ध रूप से सत्य या सिद्ध रूप से गलत हों। उनका तीसरा मानदंड, निर्णायकता, यह निर्धारित करने के लिए एक स्पष्ट यांत्रिक प्रक्रिया की मांग करता है कि कोई गणितीय कथन सही है या गलत। 1930 में एक सम्मेलन को संबोधित करते हुए, हिल्बर्ट ने घोषणा की: "हमारा नारा होगा 'हमें जानना चाहिए, हम जानेंगे।'"

ठीक एक साल बाद, गोडेल ने हिल्बर्ट के सपने को पहला झटका दिया। वह साबित कि "यह कथन अप्रमाणित है" जैसा आत्म-पराजित कथन किसी भी उपयुक्त स्वयंसिद्ध सेट से प्राप्त किया जा सकता है। यदि ऐसा कथन वास्तव में अप्रमाणित है, तो सिद्धांत अधूरा है, लेकिन यदि यह सिद्ध करने योग्य है, तो सिद्धांत असंगत है - और भी बुरा परिणाम। उसी पेपर में, गोडेल ने यह भी साबित किया कि कोई भी गणितीय सिद्धांत कभी भी अपनी स्थिरता साबित नहीं कर सकता है।

शोधकर्ताओं को अभी भी आशा है कि गणित का भविष्य का सिद्धांत, हालांकि आवश्यक रूप से अधूरा है, फिर भी निर्णय लेने योग्य साबित हो सकता है। शायद वे ऐसी प्रक्रियाएं विकसित कर सकते हैं जो गोडेल जैसे अप्रिय प्रस्तावों से दूर रहते हुए सभी सिद्ध बयानों की पहचान कर सकें। समस्या यह थी कि कोई नहीं जानता था कि इन काल्पनिक प्रक्रियाओं के बारे में कैसे तर्क किया जाए।

फिर 1936 में, एलन ट्यूरिंग नाम के एक 23 वर्षीय स्नातक छात्र ने गणना की तत्कालीन अपरिचित भाषा में हिल्बर्ट की निर्णायकता की स्थिति को दोहराया और इसे एक घातक झटका दिया। ट्यूरिंग ने एक गणितीय मॉडल तैयार किया - जिसे अब के रूप में जाना जाता है ट्यूरिंग मशीन - जो सभी संभावित एल्गोरिदम का प्रतिनिधित्व कर सकता है, और दिखाया कि यदि हिल्बर्ट की प्रक्रिया मौजूद होती, तो यह इस मॉडल के भीतर फिट होती। इसके बाद उन्होंने गोडेल जैसी स्व-संदर्भित विधियों का उपयोग किया साबित करना अनिर्णीत कथनों का अस्तित्व - या, समकक्ष, अगणनीय समस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता।

हिल्बर्ट का कार्यक्रम खंडहर हो गया: क्या साबित किया जा सकता है और क्या गणना की जा सकती है, इस पर हमेशा मौलिक सीमाएं रहेंगी। लेकिन जैसे-जैसे कंप्यूटर सैद्धांतिक अमूर्तता से वास्तविक मशीनों में विकसित हुए, शोधकर्ताओं ने महसूस किया कि ट्यूरिंग की हल करने योग्य और न सुलझने वाली समस्याओं के बीच सरल अंतर ने कई सवालों को अनुत्तरित छोड़ दिया।

1960 के दशक तक, कंप्यूटर वैज्ञानिकों ने कुछ समस्याओं को हल करने के लिए तेज़ एल्गोरिदम विकसित कर लिए थे, जबकि अन्य के लिए केवल ज्ञात एल्गोरिदम बेहद धीमे थे। क्या होगा अगर सवाल सिर्फ यह नहीं था कि क्या समस्याएं हल की जा सकती हैं, बल्कि सवाल यह था कि उन्हें हल करना कितना कठिन है?

कार्मोसिनो ने कहा, "एक समृद्ध सिद्धांत सामने आया है, और हम अब उत्तर नहीं जानते हैं।"

डायवर्जेंट पथ

यह स्पष्ट करने के लिए कि कठोरता के बारे में प्रश्न कितने उलझाने वाले हो सकते हैं, आइए ग्राफ़ से संबंधित निकट संबंधी समस्याओं की एक जोड़ी पर विचार करें। ये बिंदुओं के नेटवर्क हैं, जिन्हें नोड्स कहा जाता है, जो रेखाओं से जुड़े होते हैं, जिन्हें किनारे कहा जाता है। कंप्यूटर वैज्ञानिक उनका उपयोग हर चीज़ का मॉडल बनाने के लिए करते हैं क्वांटम गणना को यातायात का प्रवाह.

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

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

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

इस समाधान-जाँच एल्गोरिथ्म को चलाने के लिए आवश्यक समय ग्राफ़ के आकार के समानुपाती होता है। यह इसे बहुपद एल्गोरिदम की व्यापक श्रेणी में रखता है, जिसका रन समय ग्राफ़ आकार के बहुपद कार्यों के रूप में बढ़ता है। घातीय वृद्धि की तुलना में बहुपद वृद्धि स्थिर है, इसलिए बहुपद एल्गोरिदम बड़े ग्राफ़ पर भी व्यवहार्य रहते हैं। "यह नाटकीय रूप से अधिक कुशल है," कार्मोसिनो ने कहा।

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

मान लीजिए कि आपको फिर से एक ग्राफ़ दिया गया है, लेकिन अब आपसे एक "यूलेरियन पथ" खोजने के लिए कहा गया है जो हर किनारे को ठीक एक बार पार करता है। फिर, संभावित समाधानों की जाँच के लिए एक बहुपद एल्गोरिथ्म है, लेकिन इस बार समस्या को हल करने के लिए एक बहुपद एल्गोरिथ्म भी है। यहां कोई विषमता नहीं है. जटिलता सिद्धांत में, कुछ रास्ते दूसरों की तुलना में खोजना आसान लगते हैं।

हैमिल्टनियन पथ समस्या और यूलेरियन पथ समस्या दोनों जटिलता वर्ग एनपी में हैं, जिन्हें उन सभी समस्याओं को शामिल करने के लिए परिभाषित किया गया है जिनके समाधान बहुपद एल्गोरिदम द्वारा जांचे जा सकते हैं। यूलेरियन पथ समस्या भी वर्ग पी में आती है क्योंकि एक बहुपद एल्गोरिथ्म इसे हल कर सकता है, लेकिन सभी प्रतीतों के लिए, यह हैमिल्टनियन पथ समस्या के लिए सच नहीं है। ये दो ग्राफ़ समस्याएं, सतही तौर पर इतनी समान, इतने नाटकीय रूप से भिन्न क्यों होनी चाहिए? यही पी बनाम एनपी समस्या का सार है।

सार्वभौमिक रूप से कठिन

सबसे पहले, जटिलता कक्षाएं उन समस्याओं को हल करने के लिए सुविधाजनक श्रेणियों की तरह लगती थीं जो समान थीं लेकिन सीधे तौर पर संबंधित नहीं थीं - किसी को भी संदेह नहीं था कि हैमिल्टनियन पथ खोजने का अन्य कठिन कम्प्यूटेशनल समस्याओं से कोई लेना-देना है।

फिर 1971 में, संयुक्त राज्य अमेरिका में कार्यकाल से वंचित होने के बाद टोरंटो विश्वविद्यालय में स्थानांतरित होने के एक वर्ष के भीतर, जटिलता सिद्धांतकार स्टीफन कुक प्रकाशित असाधारण परिणाम. उन्होंने एक अजीब विशेषता के साथ एक विशेष एनपी समस्या की पहचान की: यदि कोई बहुपद एल्गोरिदम है जो उस समस्या को हल कर सकता है, तो यह एनपी में हर दूसरी समस्या को भी हल कर सकता है। ऐसा प्रतीत होता है कि कुक की "सार्वभौमिक" समस्या स्पष्ट रूप से कठिन समस्याओं के वर्ग को आगे बढ़ाने वाला एक अकेला स्तंभ था, जो उन्हें नीचे दी गई आसान समस्याओं से अलग करता था। उस एक समस्या को हल करें, और शेष एनपी ख़त्म हो जाएगी।

कुक को संदेह था कि उनकी सार्वभौमिक समस्या के लिए कोई तेज़ एल्गोरिदम नहीं था, और उन्होंने पेपर के बीच में ही कहा, "मुझे लगता है कि इस अनुमान को साबित करने के लिए काफी प्रयास करना उचित है।" "पर्याप्त प्रयास" एक अल्पकथन साबित होगा।

लगभग उसी समय, सोवियत संघ में एक स्नातक छात्र का नाम रखा गया लियोनिद लेविन साबित हुआ ए समान परिणाम, सिवाय इसके कि उन्होंने कई अलग-अलग सार्वभौमिक समस्याओं की पहचान की। इसके अलावा, अमेरिकी जटिलता सिद्धांतकार रिचर्ड कार्प साबित कुक (और लेविन, हालांकि कार्प और कुक को वर्षों बाद तक लेविन के काम के बारे में पता नहीं था) द्वारा पहचानी गई सार्वभौमिकता संपत्ति अपने आप में पूरी तरह से सार्वभौमिक थी। ज्ञात बहुपद एल्गोरिदम के बिना लगभग हर एनपी समस्या - यानी, लगभग हर आसानी से जांचने योग्य समस्या जो कठिन लगती थी - में एक ही संपत्ति थी, जिसे एनपी-पूर्णता के रूप में जाना जाता है।

इसका मतलब है सभी एनपी-पूर्ण समस्याएं - हैमिल्टनियन पथ समस्या, सुडोकू, और हजारों अन्य - सटीक अर्थों में समतुल्य हैं। इलंगो ने कहा, "आपके पास ये सभी अलग-अलग प्राकृतिक कार्य हैं, और वे सभी जादुई रूप से एक ही कार्य बन जाते हैं।" "और हम अभी भी नहीं जानते कि वही कार्य संभव है या नहीं।"

किसी भी एनपी-पूर्ण समस्या की कठिनाई को सुलझाना पी बनाम एनपी प्रश्न को हल करने के लिए पर्याप्त होगा। यदि पी ≠ एनपी, तो आसान और कठिन समस्याओं के बीच का अंतर हजारों स्तंभों द्वारा कायम रखा गया है जो सभी समान रूप से मजबूत हैं। यदि पी = एनपी, तो पूरी इमारत ढहने के कगार पर है, बस एक टुकड़े के गिरने का इंतजार है।

कुक, लेविन और कार्प ने कई असंबद्ध समस्याओं को एकीकृत कर दिया था। अब जटिलता सिद्धांतकारों को केवल एक समस्या का समाधान करना था: क्या P = NP है या नहीं?

पचास साल बाद भी यह प्रश्न अनुत्तरित है। काबनेट्स ने गणना की सीमाओं के बारे में तर्क की तुलना बड़ी तस्वीर की समझ के बिना एक विशाल क्षेत्र के सर्वेक्षण से की। असीमित कम्प्यूटेशनल शक्ति वाला एक प्राणी एक पहाड़ की चोटी से नीचे झांक सकता है और एक ही बार में पूरे परिदृश्य को देख सकता है, लेकिन साधारण मनुष्य इस तरह के लाभ पर भरोसा नहीं कर सकते हैं। उन्होंने कहा, "हममें से जो लोग पहाड़ के नीचे हैं वे बेहतर दृश्य के लिए ऊपर-नीचे कूदने की कोशिश कर सकते हैं।"

मान लीजिए कि P = NP. इसे साबित करने के लिए, शोधकर्ताओं को एनपी-पूर्ण समस्या के लिए एक तेज़ एल्गोरिदम खोजने की आवश्यकता होगी, जो उस विशाल परिदृश्य के कुछ अस्पष्ट कोने में छिपा हो सकता है। इसकी कोई गारंटी नहीं है कि वे इसे जल्द ही पा लेंगे: जटिलता सिद्धांतकारों को कभी-कभी ऐसा मिलता है की खोज दशकों के काम के बाद ही प्रतीत होने वाली कठिन (हालांकि एनपी-पूर्ण नहीं) समस्याओं के लिए सरल एल्गोरिदम।

अब मान लीजिए कि P≠NP. इसे साबित करना और भी कठिन लगता है। जटिलता सिद्धांतकारों को यह स्थापित करना होगा कि कोई भी तेज़ एल्गोरिदम संभवतः मौजूद नहीं हो सकता है, जो भविष्य के सभी शोधकर्ताओं के सर्वोत्तम प्रयासों को प्रभावी ढंग से पूर्वानुमानित और विफल कर सके।

यह न जानना कि कहां से शुरुआत करें, समस्या का हिस्सा है। लेकिन ऐसा नहीं है कि शोधकर्ताओं ने कोशिश नहीं की है। दशकों से उन्होंने कई कोणों से समस्या पर हमला किया है और हर मोड़ पर रास्ता अवरुद्ध पाया है। कार्मोसिनो ने कहा, "यह सैद्धांतिक कंप्यूटर विज्ञान में सबसे स्पष्ट सत्यों में से एक है।" "जब आपके पास कोई ऐसी घटना होती है जो इतनी टिकाऊ होती है, तो आप कुछ स्पष्टीकरण चाहते हैं।"

कॉलेज में कार्मोसिनो के अंतिम वर्ष तक, उनकी जिज्ञासा ने उन्हें गोडेल से जटिलता सिद्धांत में स्नातक पाठ्यक्रम तक पहुंचा दिया था। उन्हें यह जानकर आश्चर्य हुआ कि वह अपने जुनूनी प्रोजेक्ट की तुलना में होमवर्क पर अधिक समय बिता रहे थे, एक कंप्यूटर प्रोग्राम जो परियों की कहानियों की कथा संरचना को सीखेगा और नई कहानियों को उत्पन्न करेगा।

"मैंने सोचा, 'वाह, मुझे इसे गंभीरता से लेने की ज़रूरत है," कार्मोसिनो ने याद किया। कुछ ही समय में, वह इस विषय में इतना तल्लीन हो गए कि उनके गुरु ने धीरे से उन्हें अपनी स्नातकोत्तर योजनाओं पर पुनर्विचार करने का सुझाव दिया।

"वह ऐसा था, 'आप जानते हैं, यदि आप ऐसा करना जारी रखना चाहते हैं, यदि आप सैद्धांतिक कंप्यूटर विज्ञान और जटिलता सिद्धांत करना जारी रखना चाहते हैं, तो आप ऐसा कर सकते हैं: इसे ग्रेजुएट स्कूल कहा जाता है," कार्मोसिनो ने कहा। अपनी मास्टर डिग्री प्राप्त करने के बाद, वह इम्पाग्लियाज़ो की देखरेख में डॉक्टरेट की उपाधि प्राप्त करने के लिए 2012 में सैन डिएगो चले गए।

कार्मोसिनो का मुख्य लक्ष्य, सबसे पहले, बेहतर ढंग से समझना था ऐतिहासिक कागज दो दशक पहले से जिसने उनकी कल्पना पर कब्जा कर लिया था। वह पेपर, जटिलता सिद्धांतकारों द्वारा अलेक्जेंडर रज़बोरोव और स्टीवन रुडिच, ने दिखाया था कि पी ≠ एनपी साबित करने के लिए एक निश्चित "प्राकृतिक" रणनीति लगभग निश्चित रूप से विफल हो जाएगी, क्योंकि सफलता एक बड़ी कीमत पर आएगी - क्रिप्टोग्राफी का पूर्ण विघटन - जिसे शोधकर्ताओं ने बहुत ही असंभावित माना। शोधकर्ताओं ने रज़बोरोव और रुडिच के परिणाम की व्याख्या पी ≠ एनपी को साबित करने के इस लोकप्रिय दृष्टिकोण में बाधा के रूप में की।

यह "प्राकृतिक प्रमाण बाधा" जटिलता सिद्धांत में खुली समस्याओं को हल करने में कई ज्ञात बाधाओं में से एक है। प्रत्येक एक बाधा की तरह कार्य करता है, चेतावनी देता है कि एक आशाजनक प्रतीत होने वाला मार्ग वास्तव में एक मृत अंत है। साथ में, ये बाधाएँ इंगित करती हैं कि कोई भी प्रमाण जो पी बनाम एनपी समस्या का समाधान करता है, उसे अतीत में उपयोग की गई किसी भी चीज़ से मौलिक रूप से भिन्न होना होगा; इसीलिए अधिकांश शोधकर्ताओं का मानना ​​है कि समाधान अभी भी दूर है। लेकिन कम से कम बाधाएँ उन्हें बताती हैं कि किधर नहीं देखना है।

इलांगो ने कहा, "जटिलता सिद्धांत कई बाधाओं के साथ अभिशप्त और धन्य दोनों है।"

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

लेकिन प्राकृतिक प्रमाण बाधा से मेटा-जटिलता तक के मार्ग का अनुसरण करने के लिए, हमें वापस वहीं जाना होगा जहां हमने 1970 के दशक में शोधकर्ताओं को छोड़ा था, जब उन्होंने पहली बार पी बनाम एनपी समस्या से निपटना शुरू किया था। समस्याओं को कठिन साबित करना इतना कठिन क्यों हो गया?

एक घुमावदार पथ

सबसे पहले, शोधकर्ताओं ने पी ≠ एनपी को साबित करने की कोशिश की - यानी, साबित करें कि कुछ एनपी समस्याएं किसी भी संभावित बहुपद एल्गोरिदम द्वारा हल नहीं की जा सकती हैं - ट्यूरिंग द्वारा उपयोग की जाने वाली तकनीकों पर विविधताओं का उपयोग करके यह साबित करने के लिए कि कुछ समस्याएं किसी भी एल्गोरिदम द्वारा हल नहीं की जा सकती हैं। . लेकिन वे जल्दी की खोज इस बात का प्रमाण कि वे तरीके काम नहीं करेंगे - पी बनाम एनपी प्रश्न को हल करने में पहली बड़ी बाधा। इसलिए उन्होंने दूसरे दृष्टिकोण की तलाश शुरू कर दी, और जल्द ही उन्हें ट्यूरिंग के समकालीन के काम में एक दृष्टिकोण मिल गया क्लाउड शैनन.

शैनन, जो उत्तरी मिशिगन के एक छोटे से शहर में पले-बढ़े थे, सूचना युग की शुरुआत करने के लिए एक अप्रत्याशित व्यक्ति प्रतीत होते थे। फिर भी उन्होंने कंप्यूटर विज्ञान के उभरते हुए अनुशासन की अंतःविषय प्रकृति का उदाहरण दिया, इलेक्ट्रिकल इंजीनियरिंग और गणितीय तर्क में समान रूप से घरेलू महसूस किया। उसके में मास्टर की थीसिस, शैनन ने दिखाया कि कैसे इलेक्ट्रोमैकेनिकल स्विच से बने सर्किट बूलियन चर से जुड़े तार्किक अभिव्यक्तियों का प्रतिनिधित्व कर सकते हैं - मात्राएं जो केवल दो मान ले सकती हैं (जैसे कि सही या गलत, या 1 और 0)।

इन अभिव्यक्तियों में, बूलियन चर "लॉजिक गेट्स" AND, OR और NOT द्वारा एक साथ जुड़े हुए हैं। उदाहरण के लिए, प्रारंभिक अभिव्यक्ति ए और बी तब सत्य है जब ए और बी दोनों सत्य हैं, और अन्यथा गलत है; दूसरी ओर, A या B सत्य है यदि दोनों में से कम से कम एक चर सत्य है। एक NOT गेट और भी सरल है: यह एकल चर के मान को उलट देता है। इन बुनियादी बिल्डिंग ब्लॉकों की पर्याप्त मात्रा के साथ, आप कोई भी गणना कर सकते हैं।

“जब आप दिन के अंत में अपने कंप्यूटर को देखते हैं, तो यह क्या कर रहा है? यह एक सर्किट चला रहा है,” इलांगो ने कहा।

शैनन के काम ने सिद्धांतकारों को कम्प्यूटेशनल समस्याओं की कठिनाई के बारे में सोचने का एक नया तरीका सुझाया, जिसे "सर्किट जटिलता" कहा जाता है, भले ही प्रश्न में सर्किट सिर्फ गणितीय अमूर्त हैं। कुछ समय के लिए, शोधकर्ताओं ने सोचा कि यह दृष्टिकोण पी बनाम एनपी को हल करने का तरीका हो सकता है, लेकिन अंततः यह रास्ता प्राकृतिक प्रमाण बाधा के विपरीत चला गया।

सर्किट जटिलता ढांचे को ट्यूरिंग के गणना मॉडल में सबसे बुनियादी अवधारणाओं पर पुनर्विचार करने की आवश्यकता है। यहां, कम्प्यूटेशनल समस्याओं और उन्हें हल करने वाले एल्गोरिदम के बजाय, शोधकर्ता बूलियन फ़ंक्शंस और उनकी गणना करने वाले सर्किट पर विचार करते हैं। एक बूलियन फ़ंक्शन बूलियन वैरिएबल लेता है - सत्य और असत्य, 1s और 0s - और या तो सही या गलत, 1 या 0 आउटपुट देता है। और एक एल्गोरिदम की तरह, एक सर्किट किसी भी इनपुट के लिए आउटपुट उत्पन्न करने की प्रक्रिया का वर्णन करता है।

"मेरी समझ यह है कि लोगों ने सर्किट जटिलता पर काम करना शुरू कर दिया क्योंकि उन्होंने फैसला किया कि ट्यूरिंग मशीनें बहुत जटिल थीं," उन्होंने कहा रयान विलियम्स, एमआईटी में एक जटिलता सिद्धांतकार। "हम गेट दर गेट सर्किट का अध्ययन कर सकते हैं।"

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

लेकिन कई मामलों में, आप इनपुट चर की संख्या बढ़ाकर उसी फ़ंक्शन के अधिक जटिल संस्करणों पर विचार कर सकते हैं, जैसे आप बड़े ग्राफ़ पर विचार करके हैमिल्टनियन पथ समस्या को कठिन बना सकते हैं। शोधकर्ता फिर उसी प्रश्न पर विचार करते हैं जो वे एल्गोरिदम रन टाइम का अध्ययन करते समय पूछते हैं: क्या इनपुट चर की संख्या बढ़ने पर बूलियन फ़ंक्शन की गणना करने के लिए आवश्यक गेटों की न्यूनतम संख्या बहुपद या तेजी से बढ़ती है? शोधकर्ता कार्यों की इन दो श्रेणियों को क्रमशः "गणना करने में आसान" और "गणना करने में कठिन" कहते हैं।

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

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

एरोनसन ने कहा, "वहां घूमने के लिए पर्याप्त छोटे सर्किट नहीं हैं।"

इसलिए जटिलता सिद्धांतकारों ने स्वयं को एक विचित्र स्थिति में पाया। यदि लगभग हर सत्य तालिका में उच्च सर्किट जटिलता है, तो लगभग हर बूलियन फ़ंक्शन की गणना करना कठिन होगा। शोधकर्ताओं को बस एक ऐसे फ़ंक्शन की पहचान करनी थी जिसे एनपी वर्ग में भी जाना जाता था। वह कितना मुश्किल हो सकता है?

क्रिप्टो ब्रदर्स

सबसे पहले, प्रगति तीव्र थी। 1981 में, सिप्सर और दो सहयोगी साबित यदि वे गेटों की व्यवस्था कैसे की जा सकती है, इस पर कुछ प्रतिबंधों के साथ सर्किट का उपयोग करते हैं तो एक निश्चित बूलियन फ़ंक्शन की गणना करना निश्चित रूप से कठिन था।

सिप्सर ने कहा, "कल्पना यह थी कि आप इन प्रतिबंधित मॉडलों के बारे में चीजों को साबित करने में सक्षम होंगे, और फिर कम से कम प्रतिबंधों के साथ काम करना सीखा है।"

1985 में रज़बोरोव ने अगला बड़ा कदम उठाया। उन्होंने हाल ही में मॉस्को में स्नातक विद्यालय शुरू किया था और गणित की एक अलग शाखा में एक समस्या से निपटने के दौरान गलती से प्रयास में शामिल हो गए, जहां यह पता चला कि पी बनाम एनपी समस्या को हल करना एक पूर्व शर्त थी।

रज़बोरोव ने कहा, "मैं बस भाग्यशाली था कि मुझे नहीं पता था कि यह समस्या कितनी कठिन थी।" “नहीं तो शायद मैं शुरू ही नहीं कर पाता।”

रज़बोरोव ने केवल AND और OR गेट वाले सर्किट का विश्लेषण किया, और साबित ऐसे सर्किट का उपयोग करके किसी विशेष फ़ंक्शन की गणना करना कठिन था, इससे कोई फर्क नहीं पड़ता कि गेट कैसे व्यवस्थित किए गए थे - और क्या, वह फ़ंक्शन एनपी-पूर्ण माना जाता था। पी बनाम एनपी को हल करने के लिए सभी शोधकर्ताओं को रज़बोरोव की तकनीकों को नॉट गेट वाले सर्किट तक विस्तारित करना था।

रज़बोरोव ने कहा, "एक तरह की सार्वभौमिक भावना थी कि एक और कदम, एक और हमला, और हम इसे हासिल कर लेंगे।" लेकिन ऐसा नहीं हुआ. रज़बोरोव ने स्वयं साबित कर दिया कि यदि मिश्रण में नॉट गेट्स जोड़े गए तो उनकी विधि विफल हो जाएगी, और कोई भी आगे बढ़ने का दूसरा रास्ता नहीं खोज पाएगा। जैसे-जैसे साल बीतते गए, उसे आश्चर्य होने लगा कि रास्ता इतना छोटा क्यों हो गया है।

संयुक्त राज्य अमेरिका में, रुडिच इसी प्रश्न पर विचार कर रहा था। वह और इम्पाग्लिआज़ो कॉलेज के सहपाठी थे जो स्नातक विद्यालय में एक साथ गए थे। उनकी दोस्ती गोडेल और ट्यूरिंग के स्व-संदर्भित प्रमाणों और गणित और कंप्यूटर विज्ञान की नींव के लिए उनके निहितार्थ के प्रति साझा आकर्षण से उत्पन्न हुई थी।

"हमारा मज़ाक यह था कि हमें एक बटन मिलने वाला था जिस पर 'स्व-संदर्भ' लिखा हुआ था," इम्पाग्लियाज़ो ने कहा।

स्नातक छात्रों के रूप में, रुडिच और इम्पाग्लियाज़ो दोनों ने क्रिप्टोग्राफी की जटिलता-सैद्धांतिक नींव पर काम किया, एक ऐसा विषय जो पी ≠ एनपी को साबित करने के प्रयास के लिए शायद सबसे अच्छा व्यावहारिक प्रेरणा प्रदान करता है। क्रिप्टोग्राफ़र गुप्त संदेशों को "छद्म यादृच्छिकता" में छिपाकर छिपाते हैं - इस तरह से एन्क्रिप्ट किया गया संदेश किसी भी छिपकर बात करने वाले को संख्याओं की एक यादृच्छिक गड़बड़ी की तरह दिखाई देगा, लेकिन इसे अभी भी इच्छित प्राप्तकर्ता द्वारा डिकोड किया जा सकता है। लेकिन आप यह कैसे सुनिश्चित कर सकते हैं कि एक संभावित गुप्तचर के लिए कोड को तोड़ना बहुत मुश्किल होगा?

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

अपने आप में आकर्षक होते हुए भी, क्रिप्टोग्राफी उन स्व-संदर्भित तर्कों से बहुत दूर लग रही थी, जिन्होंने सबसे पहले रुडिच और इम्पाग्लियाज़ो को इस क्षेत्र में खींचा था। लेकिन जब रुडिच को यह समझने में संघर्ष करना पड़ा कि सर्किट जटिलता दृष्टिकोण क्यों रुका हुआ है, तो उसे एहसास होने लगा कि दोनों विषय इतने दूर नहीं थे। रणनीति शोधकर्ताओं ने यह साबित करने के अपने प्रयासों में अपनाई थी कि पी ≠ एनपी में एक आत्म-पराजित चरित्र था जो गोडेल के प्रसिद्ध प्रस्ताव की याद दिलाता है "यह कथन अप्राप्य है" - और क्रिप्टोग्राफी यह समझाने में मदद कर सकती है कि क्यों। रूस में, रज़बोरोव ने लगभग उसी समय एक समान संबंध की खोज की। ये प्राकृतिक प्रमाण बाधा के बीज थे।

प्राकृतिक प्रमाण अवरोध के मूल में तनाव यह है कि उच्च-जटिलता वाले कार्यों को कम-जटिलता वाले कार्यों से अलग करने का कार्य संदेशों को एन्क्रिप्ट करने के लिए उपयोग की जाने वाली छद्म यादृच्छिकता से वास्तविक यादृच्छिकता को अलग करने के कार्य के समान है। हम यह दिखाना चाहेंगे कि पी ≠ एनपी को साबित करने के लिए उच्च-जटिलता वाले फ़ंक्शन कम-जटिलता वाले कार्यों से स्पष्ट रूप से भिन्न होते हैं। लेकिन हम यह भी चाहेंगे कि छद्म यादृच्छिकता यादृच्छिकता से अप्रभेद्य हो, क्रिप्टोग्राफी की सुरक्षा में आश्वस्त हो। शायद हमारे पास यह दोनों तरीके से नहीं हो सकता।

एक क्रूर मजाक

1994 में, रज़बोरोव और रुडिच को एहसास हुआ कि उन्हें समान अंतर्दृष्टि प्राप्त हुई है, और उन्होंने अपने परिणामों को संयोजित करने के लिए एक साथ काम करना शुरू कर दिया। उन्होंने पहली बार देखा कि सर्किट जटिलता का उपयोग करके पी ≠ एनपी साबित करने के सभी पिछले प्रयासों ने एक ही सामान्य रणनीति अपनाई थी: एनपी-पूर्ण बूलियन फ़ंक्शन की एक विशेष संपत्ति की पहचान करें, फिर साबित करें कि कोई भी आसानी से गणना करने वाला फ़ंक्शन संभवतः उस संपत्ति को साझा नहीं कर सकता है। इससे पता चलता है कि चुने गए एनपी-पूर्ण फ़ंक्शन की गणना करना वास्तव में कठिन था, जिससे पी ≠ एनपी साबित होता है।

सिप्सर, रज़बोरोव और अन्य ने अपने अधिक सीमित परिणामों को साबित करने के लिए इसी रणनीति का सफलतापूर्वक उपयोग किया था, और हर मामले में, शोधकर्ताओं ने जिस विशेष संपत्ति की पहचान की थी, उसे अधिकांश बूलियन कार्यों द्वारा साझा किया गया था। रज़बोरोव और रुडिच ने इस मामले को संदर्भित करने के लिए "प्राकृतिक प्रमाण" शब्द गढ़ा जहां संपत्ति व्यापक रूप से साझा की गई थी, सिर्फ इसलिए कि कोई ज्ञात विकल्प नहीं था। यदि "अप्राकृतिक" प्रमाण संभव होते, तो उन्हें बहुत ही प्रतिकूल और नाम के योग्य होना पड़ता।

रज़बोरोव और रुडिच ने तब अपना मुख्य परिणाम साबित किया: पी ≠ एनपी के एक प्राकृतिक प्रमाण के लिए एक बहुत व्यापक समझ की आवश्यकता होगी कि गणना करने में आसान और गणना करने में कठिन फ़ंक्शन कैसे भिन्न होते हैं, और यह ज्ञान आसान स्पॉटिंग के लिए एक तेज़ एल्गोरिदम को भी बढ़ावा दे सकता है। -कार्यों की गणना करना, भले ही वे सतही रूप से जटिल हों। यदि जटिलता सिद्धांतकार पी ≠ एनपी के प्राकृतिक प्रमाण में सफल हो गए होते, तो उन्होंने एक मनमानी सत्य तालिका पर नज़र डालने और यह निर्धारित करने का लगभग अचूक तरीका खोज लिया होता कि क्या संबंधित फ़ंक्शन में उच्च या निम्न सर्किट जटिलता थी - तुलना में बहुत मजबूत और अधिक सामान्य परिणाम वे सिद्ध करने निकले थे।

कार्मोसिनो ने कहा, "आप लगभग मदद नहीं कर सकते, लेकिन जितना आपने सौदेबाजी की है उससे अधिक प्राप्त कर सकते हैं।"

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

इस संबंध को समझने के लिए, कई इनपुट चर वाले बूलियन फ़ंक्शन की सत्य तालिका में आउटपुट कॉलम को देखने और प्रत्येक "सही" को 1 से और प्रत्येक "गलत" को 0 से बदलने की कल्पना करें:

यदि बूलियन फ़ंक्शन में उच्च सर्किट जटिलता है, तो आउटपुट की लंबी सूची सैद्धांतिक रूप से 0s और 1s की वास्तव में यादृच्छिक स्ट्रिंग से अप्रभेद्य होगी - जो कि एक सिक्के को बार-बार उछालने से प्राप्त होती है। लेकिन यदि फ़ंक्शन में कम सर्किट जटिलता है, तो स्ट्रिंग में एक सरल, संक्षिप्त विवरण होना चाहिए, भले ही वह जटिल लगे। यह इसे क्रिप्टोग्राफी में उपयोग किए जाने वाले छद्म यादृच्छिक स्ट्रिंग के समान बनाता है, जिसका संक्षिप्त विवरण उस स्पष्ट यादृच्छिकता में छिपा हुआ गुप्त संदेश है।

तो रज़बोरोव और रुडिच के नतीजे से पता चला कि पी ≠ एनपी का कोई भी प्राकृतिक प्रमाण एक तेज़ एल्गोरिदम भी उत्पन्न करेगा जो छिपे हुए संदेशों वाले छद्म यादृच्छिक तारों को वास्तव में यादृच्छिक लोगों से अलग कर सकता है। सुरक्षित क्रिप्टोग्राफी असंभव होगी - शोधकर्ताओं ने पी ≠ एनपी साबित करके जो स्थापित करने की आशा की थी, उसके बिल्कुल विपरीत।

दूसरी ओर, यदि सुरक्षित क्रिप्टोग्राफी संभव है, तो प्राकृतिक प्रमाण पी ≠ एनपी को साबित करने के लिए एक व्यवहार्य रणनीति नहीं है - सुरक्षित क्रिप्टोग्राफी के लिए एक शर्त। संक्षेप में यह प्राकृतिक प्रमाण बाधा है। ऐसा लग रहा था जैसे जटिलता सिद्धांतकारों को एक क्रूर मजाक का सामना करना पड़ रहा हो।

"यदि आप कठोरता में विश्वास करते हैं, तो आपको विश्वास करना चाहिए कि कठोरता साबित करना कठिन है," काबनेट्स ने कहा।

मेटावर्स में

पी ≠ एनपी अनुमान के निहितार्थ और इसे साबित करने की कठिनाई के बीच का संबंध दिलचस्प था, लेकिन इसका पता लगाना मुश्किल था। एक बात के लिए, प्राकृतिक प्रमाण बाधा ने P ≠ NP को साबित करने के केवल एक दृष्टिकोण को अवरुद्ध कर दिया। दूसरे के लिए, इसने P ≠ NP को साबित करने की कठिनाई को P ≠ NP से नहीं, बल्कि सुरक्षित क्रिप्टोग्राफी के अस्तित्व से जोड़ा - एक निकट से संबंधित लेकिन बिल्कुल समकक्ष समस्या नहीं। संबंध को सही मायने में समझने के लिए, शोधकर्ताओं को मेटा-जटिलता के साथ सहज होना होगा।

विलियम्स ने कहा, "यह अंतर्ज्ञान है कि 'ओह, क्योंकि पी ≠ एनपी, यह साबित करना मुश्किल है कि पी ≠ एनपी।" "लेकिन इस अंतर्ज्ञान को समझने के लिए, आपको P ≠ NP जैसी किसी चीज़ को एक कम्प्यूटेशनल समस्या के रूप में साबित करने के कार्य के बारे में सोचना शुरू करना होगा।"

काबनेट्स ने स्नातक छात्र के रूप में यही किया। वह यूक्रेन में पले-बढ़े थे और सोवियत संघ के पतन के दो साल बाद उन्होंने कंप्यूटर विज्ञान में अपनी स्नातक की पढ़ाई पूरी की। इसके बाद हुई उथल-पुथल में, उनके पास उन सैद्धांतिक विषयों को आगे बढ़ाने के बहुत कम अवसर थे जिनमें उनकी सबसे अधिक रुचि थी।

काबनेट्स ने याद करते हुए कहा, "मैं कुछ और अकादमिक करना चाहता था।" "और मैं भी दुनिया देखने के लिए उत्सुक था।" वह ग्रेजुएट स्कूल के लिए कनाडा चले गए और यहीं पर उन्हें प्राकृतिक प्रमाण बाधा के बारे में पता चला। कार्मोसिनो की तरह, काबनेट्स भी परिणाम से स्तब्ध थे। “यह बहुत गहरा लग रहा था कि आपका यह संबंध है,” उन्होंने कहा।

2000 में, ग्रेजुएट स्कूल में अपने समय के अंत में, उन्होंने पाया कि उनके साथ बातचीत में प्राकृतिक प्रमाण बाधाएँ आती रहीं जिन-यी कै, एक जटिलता सिद्धांतकार जो उस समय विश्राम पर टोरंटो का दौरा कर रहा था। उन्होंने बाधा को एक बाधा के रूप में नहीं बल्कि एक निमंत्रण के रूप में देखना शुरू कर दिया - यह जांचने का एक अवसर कि समस्याओं को कठिन साबित करना कितना कठिन है। काग़ज़ जिसमें उन्होंने बताया कि यह नया परिप्रेक्ष्य मेटा-कॉम्प्लेक्सिटी के उभरते क्षेत्र में सबसे प्रभावशाली प्रारंभिक कार्यों में से एक बन जाएगा।

काबनेट्स और कै के पेपर ने रज़बोरोव और रुडिच के प्राकृतिक प्रमाण बाधा के निर्माण में निहित एक कम्प्यूटेशनल समस्या पर प्रकाश डाला: एक बूलियन फ़ंक्शन की सत्य तालिका को देखते हुए, यह निर्धारित करें कि इसमें उच्च या निम्न सर्किट जटिलता है या नहीं। उन्होंने इसे न्यूनतम सर्किट आकार समस्या, या एमसीएसपी करार दिया।

एमसीएसपी एक सर्वोत्कृष्ट मेटा-जटिलता समस्या है: एक कम्प्यूटेशनल समस्या जिसका विषय ग्राफ सिद्धांत या कोई अन्य बाहरी विषय नहीं है, बल्कि जटिलता सिद्धांत ही है। वास्तव में, यह उस प्रश्न के मात्रात्मक संस्करण की तरह है जिसने जटिलता सिद्धांतकारों को 1980 के दशक में सर्किट जटिलता दृष्टिकोण का उपयोग करके पी बनाम एनपी से निपटने के लिए प्रेरित किया: कौन से बूलियन फ़ंक्शन की गणना करना कठिन है, और कौन से आसान हैं?

"अगर हम एक एमसीएसपी एल्गोरिथ्म के साथ आए, तो यह जटिलता सिद्धांत में हम जो कर रहे हैं उसे स्वचालित करने का एक तरीका होगा," इम्पाग्लियाज़ो ने कहा। "इससे हमें कम से कम यह जबरदस्त जानकारी मिलनी चाहिए कि हम अपना काम बेहतर तरीके से कैसे करें।"

जटिलता सिद्धांतकार इस जादुई एल्गोरिदम के बारे में चिंता नहीं करते हैं जो उन्हें काम से बाहर कर देगा - उन्हें नहीं लगता कि यह बिल्कुल भी अस्तित्व में है, क्योंकि रज़बोरोव और रुडिच ने दिखाया है कि कम-जटिलता वाले से उच्च-जटिलता सत्य तालिकाओं को अलग करने के लिए ऐसा कोई भी एल्गोरिदम क्रिप्टोग्राफी बना देगा असंभव। इसका मतलब है कि एमसीएसपी संभवतः एक कठिन कम्प्यूटेशनल समस्या है। लेकिन यह कितना कठिन है? क्या यह एनपी-पूर्ण है, हैमिल्टनियन पथ समस्या और लगभग हर अन्य समस्या की तरह, जिससे शोधकर्ताओं ने 1960 के दशक में संघर्ष किया था?

एनपी में समस्याओं के लिए, "यह कितना कठिन है?" आमतौर पर उत्तर देना काफी आसान होता है, लेकिन एमसीएसपी एक अजीब बात लगती है। काबनेट्स ने कहा, "हमारे पास बहुत कम 'फ्लोटिंग' समस्याएं हैं जो एनपी-पूर्ण समस्याओं के इस द्वीप से जुड़ी नहीं हैं, भले ही वे कठिन लगती हैं।"

काबनेट्स को पता था कि वह और कै उस समस्या पर विचार करने वाले पहले व्यक्ति नहीं थे जिसे उन्होंने एमसीएसपी करार दिया था। विभिन्न कम्प्यूटेशनल समस्याओं की आंतरिक कठिनाई को समझने के शुरुआती प्रयास में, सोवियत गणितज्ञों ने 1950 के दशक की शुरुआत में एक समान समस्या का अध्ययन किया था। 1960 के दशक के अंत में एनपी-पूर्णता का सिद्धांत विकसित करते समय लियोनिद लेविन ने इसके साथ संघर्ष किया था, लेकिन वह इसे एनपी-पूर्ण साबित नहीं कर सके, और उन्होंने इसके बिना अपना मौलिक पेपर प्रकाशित किया।

उसके बाद, समस्या ने 30 वर्षों तक बहुत कम ध्यान आकर्षित किया, जब तक कि काबनेट्स और कै ने प्राकृतिक प्रमाण बाधा से इसके संबंध पर ध्यान नहीं दिया। काबनेट्स को स्वयं इस प्रश्न का समाधान करने की उम्मीद नहीं थी - इसके बजाय वह यह पता लगाना चाहते थे कि यह साबित करना इतना कठिन क्यों था कि कम्प्यूटेशनल कठोरता के बारे में यह प्रतीत होने वाली कठिन समस्या वास्तव में कठिन थी।

"यह, एक अर्थ में, मेटा-मेटा-जटिलता है," ने कहा राहुल संथानमऑक्सफ़ोर्ड विश्वविद्यालय में एक जटिलता सिद्धांतकार।

लेकिन क्या इसकी कठोरता पूरी तरह से कम हो गई थी, या कम से कम यह समझने का कोई तरीका था कि शोधकर्ता यह साबित करने में सफल क्यों नहीं हुए कि एमसीएसपी एनपी-पूर्ण था? काबनेट्स ने पाया कि, हाँ, एक कारण था: सर्किट जटिलता को समझने की कठिनाई एमसीएसपी की एनपी-पूर्णता को साबित करने के लिए किसी भी ज्ञात रणनीति में बाधा की तरह काम करती है - एक समस्या जो स्वयं सर्किट जटिलता को समझने की कठिनाई के बारे में है। प्राकृतिक प्रमाण अवरोध का विकृत, आत्म-पराजित तर्क अपरिहार्य लग रहा था।

यह भी संभव है कि एमसीएसपी एनपी-पूर्ण न हो, लेकिन वह भी असंभावित लगता है - समस्या के कुछ सरल रूप पहले से ही एनपी-पूर्ण माने जाते हैं।

इम्पाग्लिआज़ो ने कहा, "हमारे पास इसे रखने के लिए कोई अच्छी जगह नहीं है जो सीधे तौर पर हमारे द्वारा अध्ययन की गई अन्य सभी समस्याओं से संबंधित हो।"

काबनेट्स ने एमसीएसपी के अजीब व्यवहार पर प्रकाश डाला था, लेकिन उसे नहीं पता था कि आगे कैसे प्रगति की जाए। मेटा-जटिलता अनुसंधान धीमा हो गया। यह 16 साल बाद फिर से पनपेगा, जब शोधकर्ताओं ने एक और बुनियादी सवाल के साथ एक आश्चर्यजनक संबंध खोजा: यदि आप ज्यादातर समय केवल सही उत्तर पाने की परवाह करते हैं तो समस्याओं को हल करना कितना कठिन है?

दुनिया युद्ध

रोजमर्रा की समस्याओं के लिए, अधिकांश समय काम आने वाले उत्तर अक्सर काफी अच्छे होते हैं। उदाहरण के लिए, हम सामान्य ट्रैफ़िक पैटर्न के अनुसार अपनी यात्रा की योजना बनाते हैं, न कि सबसे खराब स्थिति के लिए।

अधिकांश जटिलता सिद्धांतकारों को संतुष्ट करना कठिन होता है: वे किसी समस्या को आसान घोषित करने में तभी संतुष्ट होते हैं जब वे एक तेज़ एल्गोरिदम ढूंढ सकें जो हर संभावित इनपुट पर सही उत्तर प्राप्त कर सके। वह मानक दृष्टिकोण समस्याओं को उस अनुसार वर्गीकृत करता है जिसे शोधकर्ता "सबसे खराब स्थिति" जटिलता कहते हैं। लेकिन "औसत-केस" जटिलता का एक सिद्धांत भी है, जिसमें समस्याओं को आसान माना जाता है यदि कोई तेज़ एल्गोरिदम है जो अधिकांश इनपुट पर सही उत्तर देता है।

क्रिप्टोग्राफ़रों के लिए यह अंतर मायने रखता है। एक कम्प्यूटेशनल समस्या की कल्पना करें जिसे लगभग हर इनपुट के लिए हल करना आसान है, कुछ जिद्दी मामलों को छोड़कर जहां सबसे अच्छा एल्गोरिदम विफल हो जाता है। सबसे खराब स्थिति जटिलता सिद्धांत मानता है कि यह एक कठिन समस्या है, फिर भी क्रिप्टोग्राफी के लिए यह बेकार है: यदि आपके केवल कुछ संदेशों को समझना मुश्किल है, तो इसका क्या मतलब है?

यह वास्तव में लेविन ही थे जिन्होंने एनपी-पूर्णता पर अपने अग्रणी काम के एक दशक बाद औसत-मामले की जटिलता का कठोर अध्ययन शुरू किया था। बीच के वर्षों में, वह सोवियत अधिकारियों के चक्कर में पड़ गया था - वह एक अपमानजनक उपद्रवी था जो कभी-कभी अपने कम्युनिस्ट पार्टी के युवा समूह में देशभक्ति गतिविधियों को कमजोर कर देता था। 1972 में, स्पष्ट राजनीतिक कारणों से उन्हें डॉक्टरेट की उपाधि से वंचित कर दिया गया था।

"एक युवा शोधकर्ता के रूप में सोवियत संघ में सफल होने के लिए, आप बहुत अधिक मनमौजी नहीं हो सकते, और यह कल्पना करना कठिन है कि लियोनिद भी मनमौजी न हों," इम्पाग्लिआज़ो ने कहा।

लेविन 1978 में संयुक्त राज्य अमेरिका चले गए और 1980 के दशक के मध्य में उन्होंने अपना ध्यान औसत-मामले की जटिलता की ओर लगाया। उन्होंने सिद्धांत को और विकसित करने के लिए दूसरों के साथ काम करना शुरू किया, जिसमें उस समय स्नातक छात्र इम्पाग्लियाज़ो भी शामिल था। लेकिन जैसे-जैसे उन्होंने प्रगति की, इम्पाग्लिआज़ो ने पाया कि शोधकर्ता अक्सर एक-दूसरे से बात करते थे। वह सभी को एक ही पृष्ठ पर लाना चाहता था, और इससे कोई मदद नहीं मिली कि लेविन के कागजात प्रसिद्ध रूप से संक्षिप्त थे - वह जो क्षेत्र की शुरुआत की औसत-मामले की जटिलता दो पृष्ठों से कम लंबी थी।

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

RSI काग़ज़, 1995 में प्रकाशित, एक त्वरित क्लासिक बन गया। इम्पाग्लिआज़ो ने सनकी नाम गढ़े पाँच लोक कम्प्यूटेशनल कठोरता की विभिन्न डिग्री और विभिन्न क्रिप्टोग्राफ़िक क्षमताओं द्वारा प्रतिष्ठित। हम इनमें से एक दुनिया में रहते हैं, लेकिन हम नहीं जानते कि कौन सी है।

जब से इम्पाग्लिआज़ो का पेपर सामने आया है, शोधकर्ताओं ने उसके लघु मल्टीवर्स के कुछ हिस्सों को खत्म करने का सपना देखा है - यह साबित करके संभावनाओं की जगह को कम कर दिया है कि कुछ दुनियाएं आखिरकार संभव नहीं हैं। दो दुनिया विशेष रूप से आकर्षक लक्ष्य हैं: वे जहां पी ≠ एनपी के बावजूद क्रिप्टोग्राफी असंभव है।

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

ये दोनों दुनियाएं मेटा-कॉम्प्लेक्सिटी समस्याओं से निकटता से जुड़ी हुई हैं - विशेष रूप से, ह्यूरिस्टिका का भाग्य लंबे समय से चले आ रहे सवाल से जुड़ा है कि क्या एमसीएसपी एनपी-पूर्ण है। वह प्रश्न जिसने बहुत समय पहले कबानेट्स को आकर्षित किया था और लेविन को स्तब्ध कर दिया था, वह महज जिज्ञासा नहीं है: पूरी दुनिया दांव पर है।

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

लेकिन दुनिया को नष्ट करना कोई छोटी उपलब्धि नहीं है। 2003 में, दो जटिलता सिद्धांतकार पता चला ज्ञात एनपी-पूर्ण समस्याओं के लिए औसत-मामले में कटौती को सबसे खराब साबित करने के लिए मौजूदा दृष्टिकोण विचित्र परिणाम देंगे, यह सुझाव देते हुए कि ऐसे सबूत शायद संभव नहीं हैं।

शोधकर्ताओं को एक और दृष्टिकोण ढूंढना होगा, और अब वे सोचते हैं कि एमसीएसपी ही वह समस्या हो सकती है जिसकी उन्हें आवश्यकता है। लेकिन यह एक दशक से अधिक समय तक स्पष्ट नहीं होगा। कनेक्शन की पहली झलक मार्को कार्मोसिनो के प्राकृतिक प्रमाण अवरोध के प्रति लगातार आकर्षण से उभरी।

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

कार्मोसिनो ने कहा, "उस समय मैं उस पेपर के प्रति जुनूनी था।" "कुछ नहीं बदला है।"

कैलिफोर्निया विश्वविद्यालय, बर्कले में एक सेमेस्टर-लंबी कार्यशाला की यात्रा के दौरान अंततः उनका जुनून फलीभूत हुआ, जहां उन्होंने अपना अधिकांश समय इम्पाग्लियाज़ो, काबनेट्स और से बात करने में बिताया। एंटोनिना कोलोकोलोवामेमोरियल यूनिवर्सिटी ऑफ़ न्यूफ़ाउंडलैंड के एक जटिलता सिद्धांतकार, जिन्होंने 2013 के पेपर पर काबनेट्स के साथ सहयोग किया था। कार्मोसिनो ने पहले भी एक बार उन तीनों के साथ काम किया था, और उस सफल सहयोग ने उन्हें उस विषय के बारे में सवाल पूछने का आत्मविश्वास दिया जो उन्हें सबसे ज्यादा आकर्षित करता था।

"वह लोगों को अच्छे तरीके से परेशान कर रहा था," काबनेट्स ने याद किया।

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

में 2016 कागज, चार शोधकर्ताओं ने साबित किया कि एक निश्चित प्रकार के औसत-केस एमसीएसपी एल्गोरिदम का उपयोग अंकों के यादृच्छिक दिखने वाले तारों में छिपे पैटर्न की पहचान करने के लिए सबसे खराब स्थिति वाले एल्गोरिदम का निर्माण करने के लिए किया जा सकता है - एक कार्य जिसे कंप्यूटर वैज्ञानिक "सीखना" कहते हैं। यह एक आश्चर्यजनक परिणाम है क्योंकि एमसीएसपी एल्गोरिदम द्वारा निष्पादित बाइनरी वर्गीकरण कार्य - उच्च जटिलता या कम जटिलता - की तुलना में सहज ज्ञान युक्त सीखना कठिन लगता है। और, आश्चर्यजनक रूप से, इसने एक कार्य की सबसे खराब स्थिति को दूसरे की औसत-मामले की जटिलता से जोड़ दिया।

इम्पाग्लिआज़ो ने कहा, "यह स्पष्ट नहीं था कि ऐसा कोई संबंध मौजूद होगा।"

एमसीएसपी के लिए एक तेज़ एल्गोरिदम सामान्य बूलियन सर्किट के लिए पूरी तरह से काल्पनिक है: यह तब तक मौजूद नहीं हो सकता जब तक कि एमसीएसपी एक आसान कम्प्यूटेशनल समस्या न बन जाए, इसके विपरीत सभी सबूतों के बावजूद, और इसका मतलब है कि चार शोधकर्ताओं के पेपर द्वारा निहित सीखने का एल्गोरिदम है समान रूप से काल्पनिक.

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

इलंगो ने कहा, "किसी तरह उनका आत्म-संदर्भित स्वाद आपको ऐसे काम करने में सक्षम बनाता है जो प्रतीत होता है कि आप अधिक मानक समस्याओं के साथ नहीं कर सकते।"

परिणाम ने अन्य विषयों पर काम कर रहे जटिलता सिद्धांतकारों का ध्यान खींचा। यह मेटा-जटिलता और औसत-मामले की जटिलता के बीच आगे के संबंधों का पूर्वावलोकन भी था जो आने वाले वर्षों में सामने आएगा।

सबसे बढ़कर, यह इस बात का प्रमाण था कि शोधकर्ता उन बाधाओं के बारे में सरल प्रश्न पूछकर कितनी दूर तक पहुँच सकते हैं जो पहली नज़र में केवल उनकी प्रगति में बाधा बनती प्रतीत होती हैं।

इम्पाग्लिआज़ो ने कहा, "इस तरह का द्वंद्व कम से कम पिछले 30 या 40 वर्षों की जटिलता का विषय है।" “बाधाएँ अक्सर अवसर बन जाती हैं।”

आंशिक ऋण

कार्मोसिनो और उनके सहयोगियों द्वारा अपना पेपर प्रकाशित करने के बाद से प्रगति में तेजी ही आई है।

कोलोकोलोवा ने कहा, "नई चीजें हो रही हैं।" "वास्तव में बहुत सारे प्रतिभाशाली जूनियर शोधकर्ता हैं।"

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

इलांगो मेटा-कॉम्प्लेक्सिटी में अपनी रुचि का श्रेय इसे देते हैं एरिक एलेन्डर, रटगर्स विश्वविद्यालय में एक जटिलता सिद्धांतकार और उन कुछ शोधकर्ताओं में से एक जिन्होंने 2000 और 2010 के दशक की शुरुआत में मेटा-जटिलता पर काम करना जारी रखा। इलंगो ने कहा, "उनका उत्साह संक्रामक था।"

एलेन्डर से प्रेरित एक और युवा शोधकर्ता हैं शुचि हिरहारा, अब टोक्यो में राष्ट्रीय सूचना विज्ञान संस्थान में प्रोफेसर हैं। 2018 में स्नातक छात्र रहते हुए, हीराहारा ने मेटा-जटिलता और औसत-केस जटिलता के बीच संबंधों की वास्तविक सीमा का खुलासा किया, जिसे कार्मोसिनो और उनके सह-लेखकों ने खोजा था। उन चार शोधकर्ताओं ने एक समस्या की औसत-मामले की जटिलता - एमसीएसपी - और दूसरी - बूलियन सीखने की सबसे खराब स्थिति की जटिलता के बीच एक संबंध पाया था। हिराहारा ने अपनी तकनीकों को और विकसित किया निकाले जाते हैं एमसीएसपी के लिए औसत-मामले में सबसे खराब स्थिति में कमी। उनके परिणाम का तात्पर्य है कि एक काल्पनिक औसत-केस एमसीएसपी एल्गोरिदम जैसा कि कार्मोसिनो और उनके सहयोगियों ने माना था कि वास्तव में बिना किसी गलती के एमसीएसपी के थोड़े अलग संस्करण को हल करने के लिए पर्याप्त शक्तिशाली होगा।

हिराहारा का परिणाम रोमांचक है क्योंकि कई शोधकर्ताओं को संदेह है कि एमसीएसपी एनपी-पूर्ण है, अन्य सभी समस्याओं के विपरीत, जिनके लिए सबसे खराब स्थिति से लेकर औसत-मामले में कटौती ज्ञात है। यदि वे सभी औसत-केस एल्गोरिदम को कवर करने के लिए हिरहारा के परिणामों का विस्तार कर सकते हैं और फिर साबित कर सकते हैं कि एमसीएसपी एनपी-पूर्ण है, तो यह साबित होगा कि हम ह्यूरिस्टिका में नहीं रहते हैं।

संथानम ने कहा, "यह वास्तव में धरती को हिला देने वाला परिणाम होगा।"

यह साबित करना कि एमसीएसपी एनपी-पूर्ण है, एक कठिन काम लग सकता है - आखिरकार, यह प्रश्न 50 वर्षों से अधिक समय से खुला है। लेकिन एक के बाद सफलता पिछले साल हिरहारा द्वारा, शोधकर्ता अब कुछ साल पहले किसी की अपेक्षा से कहीं अधिक करीब हैं।

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

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

इस परिणाम ने शोधकर्ताओं को हिराहारा के पहले के काम से भी अधिक मेटा-कॉम्प्लेक्सिटी में सक्रिय कर दिया, और अन्य शोधकर्ताओं ने भी नोटिस लिया - जटिलता सिद्धांतकार और ब्लॉगर लांस फोर्टनो ने इसे डब किया वर्ष का परिणाम. ऐसा इसलिए है क्योंकि कम्प्यूटेशनल समस्याओं के ऐसे "आंशिक फ़ंक्शन" संस्करणों से निपटना अन्य एनपी-पूर्णता प्रमाणों में एक महत्वपूर्ण मध्यवर्ती कदम रहा है।

विलियम्स ने कहा, "यह अद्भुत काम है।" "हर किसी ने सोचा कि ये आंशिक समस्याएं लगभग पूरी समस्या के समान ही कठिनाई थीं।"

एमसीएसपी के पूर्ण संस्करण के लिए एनपी-पूर्णता साबित करने में बाधाएँ बनी हुई हैं। लेकिन ऐसी कोई भी बाधा नहीं है जो यह सुझाव दे कि एक पूरी तरह से नए टूलकिट की आवश्यकता है - यह केवल ज्ञात तकनीकों को संयोजित करने का सही तरीका खोजने का मामला हो सकता है। एक प्रमाण अंततः उन कुछ समस्याओं में से एक की स्थिति का समाधान कर देगा जिन्होंने तब तक वर्गीकरण का विरोध किया है जब तक जटिलता सिद्धांत अस्तित्व में है। ईमेल पर, लेविन ने लिखा: "यह मुझे यह दिखाने में नम्रता देगा कि मैं इसे देखने में सक्षम न होने के कारण मूर्ख था :-)।"

गुम हुए टुकड़े

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

"पहेली के विभिन्न टुकड़े गायब हैं," पास ने कहा। "मेरे लिए यह बिल्कुल जादुई है कि ये क्षेत्र इतनी गहराई से जुड़े हुए हैं।"

हिरहारा ने चेतावनी दी है कि 30 साल पहले रची गई इम्पाग्लियाज़ो दुनिया को ख़त्म करने के इरादे से शोधकर्ताओं के लिए चुनौतियाँ अभी भी इंतज़ार में हैं। उन्होंने कहा, "मैं यह कहना चाहूंगा कि कुछ बिंदु पर ह्यूरिस्टिका और पेसिलैंड को खारिज कर दिया जाएगा, लेकिन मुझे यकीन नहीं है कि हम कितने करीब हैं।"

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

उन्होंने कहा, "मैं खुद को बहुत अधिक आस्तिक नहीं बनने देने की कोशिश करता हूं क्योंकि कुछ भी काम नहीं करने का एक बहुत अच्छी तरह से स्थापित ट्रैक रिकॉर्ड है।" "लेकिन हम बहुत सारे रोमांचक विकास देख रहे हैं - बाधाओं की तरह दिखने वाली चीजों को दूर करने के तरीके।"

यदि कोई एक सबक है जो शोधकर्ताओं ने पी बनाम एनपी प्रश्न का उत्तर देने के लिए अपने संघर्षों से सीखा है - या यहां तक ​​​​कि इसे समझें - तो वह यह है कि जटिलता सिद्धांत स्वयं जटिल है। लेकिन वह चुनौती ही वास्तव में इस खोज को इतना फायदेमंद बनाती है।

कार्मोसिनो ने कहा, "यह वास्तव में बहुत अच्छा है कि यह इतना कठिन है।" "मैं कभी बोर नहीं होने वाला।"

संपादक का नोट: स्कॉट एरोनसन इसके सदस्य हैं क्वांटा पत्रिकाहै सलाहकार बोर्ड.