शोधकर्ता जो नई दुनिया की कल्पना करके गणना की खोज करता है | क्वांटा पत्रिका

कल्पना कीजिए कि आप गणना की प्रकृति को समझने की खोज में हैं। आप गहरे जंगल में हैं, किसी भी रास्ते से बहुत दूर हैं, और गूढ़ संदेश आपके चारों ओर पेड़ों के तनों में उकेरे गए हैं - बीपीपी, एसी⁰[एम], Σ₂पी, वाईएसीसी, और सैकड़ों अन्य। ग्लिफ़ आपको कुछ बताने की कोशिश कर रहे हैं, लेकिन शुरुआत कहां से करें? आप उन सभी को सीधा भी नहीं रख सकते।

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

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

और ये एकमात्र ऐसी दुनिया नहीं है जिसका उसने सपना देखा है। इम्पाग्लिआज़ो आजीवन टेबलटॉप रोल-प्लेइंग गेम जैसे डंगऑन और ड्रेगन का प्रशंसक रहा है, और उसे आविष्कार करने में खुशी होती है नियमों के नए सेट और तलाशने के लिए नई सेटिंग्स। वही चंचल भावना कामचलाऊ कॉमेडी के उनके 30 साल के अभ्यास को जीवंत करती है।

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

क्वांटा कठिन समस्याओं और कठिन पहेलियों के बीच अंतर, परामर्श दैवज्ञ और कामचलाऊ कॉमेडी के गणितीय पाठों के बारे में इम्पाग्लिआज़ो से बात की। स्पष्टता के लिए साक्षात्कार को संक्षिप्त और संपादित किया गया है।

आपको पहली बार गणित में रुचि कब हुई?

मुझे गणित में तब से रुचि थी, जब मैं वास्तव में जानता था कि यह क्या है। तीसरी कक्षा में, मेरे गणित के ग्रेड कम होने लगे क्योंकि हमें गुणन सारणी याद करनी थी, और मैंने मना कर दिया। मेरी माँ ने कहा, "लेकिन रसेल, तुम्हें गणित पसंद है, तुम ऐसा क्यों नहीं करते?" और मैंने कहा, “यह गणित नहीं है, यह याद रखना है। वास्तविक गणित में याद रखना शामिल नहीं है।” उस समय मैंने जो कुछ भी सीखा था वह अंकगणित था, इसलिए मुझे यकीन नहीं है कि मुझे यह धारणा कहां से मिली कि गणित अमूर्त अवधारणाओं के बारे में है।

कंप्यूटर विज्ञान के बारे में क्या? क्षेत्र के हिस्से बहुत अमूर्त हैं, लेकिन वे वे नहीं हैं जिनसे अधिकांश लोग पहली बार रूबरू होते हैं।

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

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

आपके कुछ सबसे प्रसिद्ध कार्य क्रिप्टोग्राफी और कम्प्यूटेशनल जटिलता सिद्धांत के बीच संबंधों का पता लगाते हैं। वे दो क्षेत्र संबंधित क्यों हैं?

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

समस्या और पहेली में क्या अंतर है?

सामान्य तौर पर, समस्या प्रस्तुत करने वाले व्यक्ति को शायद इसका उत्तर नहीं पता हो। पहेली एक समस्या है जिसे उत्तर को ध्यान में रखकर तैयार किया गया है। तो हमें पहेली की आवश्यकता क्यों है? क्योंकि हमें यह निर्धारित करने में सक्षम होने की आवश्यकता है कि जिस व्यक्ति ने कथित तौर पर इसे हल किया था, उसने वास्तव में ऐसा किया था या नहीं। रोजमर्रा की जिंदगी में, हम मनोरंजन के लिए पहेलियों का उपयोग करते हैं, लेकिन हम उनका उपयोग कक्षाओं में यह जांचने के लिए भी करते हैं कि लोगों को सामग्री समझ में आई या नहीं। क्रिप्टोग्राफी में यही होता है: हम किसी के ज्ञान का परीक्षण करने के लिए पहेलियों का उपयोग कर रहे हैं।

पांचों दुनियाओं के बीच अंतर यह है कि वे "क्या कठिन समस्याएं हैं?" प्रश्नों का उत्तर कैसे देते हैं। और "क्या कठिन पहेलियाँ हैं?"

वे अलग-अलग उत्तर कैसे चलते हैं?

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

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

आपको फाइव वर्ल्ड्स पेपर लिखने के लिए किसने प्रेरित किया?

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

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

तो फिर इसे विचित्र नामों वाली अलग-अलग दुनियाओं के रूप में क्यों प्रस्तुत किया जाए?

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

क्या शोधकर्ताओं ने पांच संभावित दुनियाओं में से किसी को खारिज कर दिया है?

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

काल्पनिक दुनिया भी जटिलता सिद्धांत में एक और भूमिका निभाती है, सबूतों में जो "दैवज्ञ" के अस्तित्व को मानते हैं। तो, सबसे पहले, दैवज्ञ वास्तव में क्या है?

कल्पना कीजिए कि कोई व्यक्ति एक अनोखा उपकरण बनाता है जो किसी समस्या को हल कर सकता है, बिना हमें उस समस्या को हल करने के लिए कोई एल्गोरिदम जाने। दैवज्ञ यही है. यदि हमारे पास ऐसा कोई चमत्कारी उपकरण हो और हम इसे अपने कंप्यूटर के अंदर रखें, तो यह गणना योग्य और गैर गणना योग्य के बीच की रेखा को स्थानांतरित कर सकता है।

क्या शोधकर्ताओं को लगता है कि ये जादुई बक्से वास्तव में मौजूद हो सकते हैं?

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

आपने कम्प्यूटेशनल कठोरता और यादृच्छिकता के बीच संबंध भी खोजे हैं। वह कनेक्शन कैसे काम करता है?

यह वास्तव में यह कहने का एक तरीका है कि यदि आप कुछ नहीं समझते हैं, तो यह यादृच्छिक लग सकता है। मान लीजिए मैं कहता हूं कि मैं एक और हजार के बीच की संख्या के बारे में सोच रहा हूं। यदि मैं यादृच्छिक रूप से संख्या चुनता हूं, तो आपके पास इसका अनुमान लगाने का एक हजार में से एक मौका होता है। और अगर मैं पूछूं - मोंटी पाइथॉन का अनुसरण करते हुए - "मील प्रति घंटे में, एक यूरोपीय निगल की औसत हवाई गति क्या है?" आपको लगभग वही मौका मिला है। यह संभवतः प्रति घंटे एक मील से अधिक चलती है, और संभवतः यह प्रति घंटे एक हजार मील से अधिक नहीं चलती है।

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

तो अंतर्दृष्टि यह है कि कठिन समस्याएं जिनके समाधान हम नहीं जानते हैं वे "छद्म आयामी" संख्याओं का स्रोत प्रदान कर सकते हैं जो यादृच्छिक दिखती हैं।

मोंटी पाइथॉन के बारे में बोलते हुए, मुझे पता है कि आप लंबे समय से कामचलाऊ कॉमेडी कर रहे हैं - आपकी शुरुआत कैसे हुई?

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

उसने क्या सोचा?

वह कहती है कि मैं सचमुच बहुत भयानक थी। जब आप एक तर्कशास्त्री होते हैं, तो आपको हमेशा हर शब्द की बारीकियों के बारे में सोचने के लिए प्रशिक्षित किया जाता है। आप कुछ गलत नहीं कहना चाहते. इम्प्रोव इस मायने में महान है कि यह इसे उलट देता है: मुद्दा कुछ सही कहने का नहीं है, बल्कि जल्दी से कुछ बनाने का है। यह मेरे शेष जीवन के विपरीत था।

मेरी वर्तमान पत्नी ने कक्षा से छुट्टी ले ली, और जब वह एक साल बाद वापस लौटी, तो मैं उसे प्रभावित करने में कामयाब रहा। वह 30 साल पहले की बात है. मैं अब भी उसी प्रशिक्षक के साथ वही कक्षा लेता हूँ।

क्या सुधार करने से आपके शोध करने का तरीका बदल गया है?

अपने हर विचार के बारे में अति आलोचनात्मक न होने के लिए यह अच्छा अभ्यास है। यह सहयोग में विशेष रूप से सहायक है। अन्य लोगों के साथ काम करते समय, मैं ऐसी बातें कहता था, “लेकिन वह विचार निम्नलिखित कारणों से काम नहीं करेगा। यह अक्षरशः सत्य नहीं है।” इम्प्रोव में, आपको हमेशा यह स्वीकार करना होगा कि आपका साथी क्या कहता है। और मुझे लगता है कि यह एक अच्छा रवैया है, खासकर जब आप छात्रों के साथ शोध कर रहे हों: उनकी कही गई किसी बात को सिर्फ इसलिए खारिज न करें क्योंकि आप जानते हैं कि यह गलत है। ऐसे बहुत से अच्छे विचार हैं जो 100% सही नहीं हैं।

जैसे क्या?

जब आप किसी समस्या के लिए अंतर्ज्ञान प्राप्त करने का प्रयास कर रहे हों, तो एक चीज़ जो मदद करती है वह है कुछ सरलीकृत धारणाओं के साथ शुरुआत करना। वे धारणाएँ आमतौर पर सच नहीं होती हैं, लेकिन वे आपको एक रोड मैप बनाने में मदद कर सकती हैं। कहो, “अगर मेरे पास हाथी होता, तो मैं पहाड़ों पर चढ़ सकता था। निःसंदेह, मेरे पास हाथी नहीं है। लेकिन अगर मैंने ऐसा किया, तो यहां बताया गया है कि मैं इसे कैसे करूंगा। और तब आपको एहसास होता है, “ठीक है, शायद मुझे इस कदम के लिए हाथी की ज़रूरत नहीं है। एक खच्चर ठीक रहेगा।”

रोल-प्लेइंग गेम के प्रति आपके प्रेम के बारे में क्या कहना है - क्या इसने आपके काम को बिल्कुल प्रभावित किया है?

हो सकता है कि इसने मेरे पूरे शोध को प्रभावित न किया हो, लेकिन इसने निश्चित रूप से मेरे पांच विश्वों के पेपर को प्रभावित किया। मुझे हमेशा से ही फंतासी और विज्ञान कथाओं और अलग-अलग संभावित दुनियाओं के बारे में जानने में सामान्य रुचि रही है - अगर सब कुछ अलग होता तो चीजें कैसी होतीं?

काल्पनिक दुनिया का पता लगाने के लिए रोल-प्लेइंग गेम इतना आकर्षक तरीका क्यों हैं?

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