P और NP के बारे में थोड़ा और

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

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

Algorithmics

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

अनुमानी

हेयुरिस्टिक्स एक ऐसी दुनिया है जिसमें एनपी से समस्याएं सबसे खराब स्थिति में प्रभावी समाधान नहीं हैं, लेकिन आसानी से औसत पर हल की जाती हैं (कई आदानों पर कुछ संभाव्यता वितरण के लिए)।
हयूरिस्टिक्स, एक तरह से एक विरोधाभासी दुनिया है। एनपी से कार्यों के जटिल उदाहरण हैं, लेकिन इस तरह के जटिल उदाहरण को खोजना अपने आप में एक मुश्किल काम है। इस दुनिया में, प्रोफेसर ऐसे कार्यों को खोजने में सक्षम होंगे जो गॉस के लिए बहुत कठिन होंगे। लेकिन उसे एक सप्ताह एक ऐसे कार्य की तलाश में बिताना होगा जो गॉस दिन के दौरान हल नहीं कर सकता है, और एक वर्ष के लिए एक ऐसा कार्य खोजने के लिए जो गॉस एक महीने का समय बिताएगा (इस मामले में, यह माना जाता है कि गॉस के प्रोफेसर के ऊपर कुछ बहुपद हैं, क्योंकि गॉस, अंत में। प्रतिभा का)। सबसे अधिक संभावना है, जीवन इतना गंभीर नहीं है जितना कि हमें जटिल कार्य प्रदान करना है, यदि केवल जीवन रास्पबेरी नहीं लगता है। इसलिए, व्यावहारिक उद्देश्यों के लिए, यह दुनिया एल्गोरिथम से लगभग अप्रभेद्य है।
या यह अभी भी अलग है? Heuristics में, NP की किसी समस्या को हल करने का औसत समय इस समस्या पर "सोचने पर" औसत समय पर निर्भर करता है। यह स्थिति को कुछ हद तक जटिल करता है। मान लीजिए, औसतन, किसी समस्या के समाधान की गणना एक समाधान का आविष्कार करने से दो गुना लंबी है। यदि हम समस्या नंबर 1 पर सोचने के लिए समय टी पर खर्च करते हैं, तो हम समाधान की गणना पर 2T समय इकाइयों को खर्च करेंगे। इस समस्या का समाधान समस्या संख्या 2 के समाधान को प्रभावित करता है, अर्थात। हमने समस्या 2 के समाधान के बारे में सोचते हुए 3T इकाइयों का समय बिताया। इसलिए, समस्या नंबर 2 को हल करने में 6T यूनिट का समय खर्च होगा। जो समस्या संख्या 3 की ओर जाता है, जिसे हमने पहले से ही सोचने की 10T इकाइयों पर खर्च किया है, इसलिए समाधान पर 20T खर्च किया जाएगा। जैसे ही यह पुनरावृत्ति तेजी से बढ़ती है, बस कुछ ही चरणों में हम "संभव" और "अवास्तविक" के बीच की सीमा पार कर जाएंगे।
वीएलएसआई डिज़ाइन के मामले में, अब आवश्यक रूप से प्रभावी समाधान नहीं होंगे, क्योंकि इस मामले में हम उन विशिष्ट योजनाओं में बहुत रुचि नहीं रखते हैं जो विनिर्देशों को फिट करते हैं, और विशिष्ट विकल्पों को संतुष्ट करने वाले न्यूनतम विकल्प महत्वपूर्ण हैं। इस तरह की योजनाओं का अच्छा वितरण नहीं हो सकता है, और चूंकि यह उन्हें खोजने के लिए सबसे अधिक संभावना समय लेगा, इस बात की कोई गारंटी नहीं है कि वे "सबसे खराब मामले" नहीं हैं, जिस पर हेयुरिस्टिक में एल्गोरिदम अच्छी तरह से काम नहीं करते हैं।
क्रिप्टोग्राफी और नेटवर्क सुरक्षा में अल्गोरिदमिक्स के साथ कोई बुनियादी अंतर नहीं होगा। यह बहुत कम उपयोग होगा यदि कर्तव्यनिष्ठ उपयोगकर्ता किसी ऐसे कार्य के उदाहरण को खोजने में बहुत समय व्यतीत करते हैं जो उन्हें विशिष्ट रूप से पहचान सकता है, जब कोई हमलावर इस उदाहरण को तुलनीय मात्रा में हल कर सकता है (यह माना जाता है कि एक हमलावर जो सिस्टम को क्रैक करना चाहता है, वह संसाधनों का काफी अधिक उपयोग करता है। ईमानदार उपयोगकर्ता)।

Pessilandiya

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

Minikript

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

Kriptomaniya

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

आर। इम्पेग्लियाज़ो, " औसत-मामले की जटिलता का एक निजी दृष्टिकोण ," sct, pp। 134, 10 वें वार्षिक संरचना में जटिलता सिद्धांत सम्मेलन (SCT'95), 1995

XKCD वेबसाइट से ली गई छवि।