"क्या सबूत है?": सैद्धांतिक कंप्यूटर विज्ञान से एक दृश्य

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



यह समझाने के लिए कि हम किस तरह के सबूतों के बारे में बात कर रहे हैं, एक उदाहरण पर विचार करें: एक कंप्यूटर प्रोग्राम है जिसके लेखक दावा करते हैं कि कार्यक्रम कुछ विशिष्ट करता है (विशिष्ट उदाहरण थोड़ा बाद में होगा)। आप कार्यक्रम को चला सकते हैं और एक उत्तर प्राप्त कर सकते हैं। और आप यह कैसे सुनिश्चित कर सकते हैं कि कार्यक्रम वह करता है जो उसे करना चाहिए? यह अच्छा होगा यदि, उत्तर के अलावा, कार्यक्रम सबूत प्रदान करेगा कि यह उत्तर सही है।

एक अधिक विशिष्ट उदाहरण पर विचार करें: हम एक ऐसा कार्यक्रम करना चाहते हैं जो अपने अधिकतम के एक प्रमाण के साथ एक द्विपदीय ग्राफ में अधिकतम आकार के मिलान का पता लगाएं।



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

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



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

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

इस लेख में हम प्रमेयों के स्वत: प्रमाण और कार्यक्रमों की शुद्धता के प्रमाण पर स्पर्श नहीं करेंगे, हालाँकि ये विषय भी काफी रोचक हैं।

क्या सबूत की जरूरत है?

एक भाषा कुछ परिमित वर्णमाला पर रेखाओं का एक समूह है। सैद्धांतिक कंप्यूटर विज्ञान में, आमतौर पर x isL के कथनों के साक्ष्य पर विचार किया जाता है, जहाँ L भाषा है और x कुछ स्ट्रिंग है। इस प्रकार के कथन गणितीय प्रमेयों का सामान्यीकरण करते हैं, क्योंकि किसी भी गणितीय प्रमेय में कहा गया है कि औपचारिक भाषा में लिखा गया एक बयान कई सच्चे बयानों से संबंधित है।

भाषा एल के लिए प्रूफ सिस्टम एल्गोरिदम ए (एक्स, डब्ल्यू) है, जो इनपुट की दो लाइनें प्राप्त करता है: एक्स और डब्ल्यू और यह जांचता है कि लाइन डब्ल्यू एक्सएएल की सदस्यता का प्रमाण है। सबूत प्रणाली के लिए दो गुणों की आवश्यकता होती है: शुद्धता और पूर्णता। सुधार बताता है कि अगर कुछ तार के लिए x और w एल्गोरिथ्म A (x, w) 1 उपज देता है, तो x ifL। संपूर्णता बताती है कि प्रत्येक x∈L के लिए एक पंक्ति w मौजूद है जैसे कि एल्गोरिथ्म A (x, w) 1 उत्पन्न करता है।

जिन भाषाओं के लिए साक्ष्य प्रणाली मौजूद है, उन्हें प्रगणित भाषाएं कहा जाता है। यदि आप एक enumerated भाषा की एक और परिभाषा के साथ आए, तो एक अभ्यास के रूप में, उनकी तुल्यता साबित करें।

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

संक्षिप्त साक्ष्य

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


हम कहते हैं कि एक भाषा L, वर्ग NP से संबंधित है यदि उसके लिए एक प्रभावी प्रूफ सिस्टम है और बहुपद p ऐसा है कि किसी भी x thatL के लिए एक प्रमाण है कि x∈L, p ((x | x) से अधिक लंबाई का है। एक भाषा L वर्ग P से संबंधित है यदि कोई बहुपद-कालिक एल्गोरिथ्म मौजूद है जो यह जांचता है कि इनपुट स्ट्रिंग L से संबंधित है। कक्षा P, वर्ग NP में समाहित है, क्योंकि P से प्रत्येक भाषा L के लिए, एल्गोरिथ्म जो L की जाँच करता है, वह स्वयं एक प्रमाण प्रणाली होगी यदि हम विचार करें। कि वह प्रमाण की उपेक्षा करता है। यह वर्तमान में अज्ञात है कि क्या वर्ग एनपी की भाषाएं मौजूद हैं जो कक्षा पी से संबंधित नहीं हैं। क्ला और पी। और एनपी की समानता का प्रश्न क्ले संस्थान द्वारा संकलित सात सहस्राब्दी समस्याओं की सूची में शामिल है; इस समस्या के समाधान के लिए एक मिलियन डॉलर के पुरस्कार की घोषणा की गई है। जी। पेरेलमैन द्वारा पॉइंकेयर अनुमान के प्रमाण के संबंध में मिलेनियम टास्क लिस्ट के बारे में बहुतों ने सुना है। अधिकांश विशेषज्ञों का मानना ​​है कि कक्षाएं पी और एनपी संयोग नहीं करती हैं।

एनपी वर्ग की भाषाओं के उदाहरणों पर विचार करें:

• समग्र संख्याओं की भाषा वर्ग एनपी में निहित है। यह साबित करने के लिए कि संख्या n समग्र है, यह दो पूर्णांक a और b को प्रस्तुत करने के लिए पर्याप्त है, जो एक और n = ab से अधिक हैं। अपराधों की भाषा भी एनपी श्रेणी में है, लेकिन इसे साबित करना अधिक कठिन है। हालांकि, 2002 में, कयाल और सक्सेना ने साबित कर दिया कि सरल भाषा की भाषा (और इसलिए, समग्र) संख्या पी में निहित है।
  
• जीआई भाषा पर विचार करें, जिसमें आइसोमोर्फिक ग्राफ़ के जोड़े शामिल हैं। हम मानते हैं कि रेखांकन के कोने 1 से n तक गिने जाते हैं, प्रत्येक
  एक किनारे बिल्कुल एक जोड़ी को जोड़ता है। दो ग्राफ G ₁ (V ₁ , E ₁ ) और G ₂ (V ₂ , E ₂ ) को आइसोमॉर्फिक कहा जाता है यदि पहले ग्राफ के शीर्षों को फिर से जोड़ा जा सकता है ताकि पहला ग्राफ दूसरे ग्राफ के साथ मेल खाता हो। इसका मतलब यह है कि पुन: आकार देने के बाद, पहले ग्राफ के किनारों का सेट दूसरे ग्राफ के किनारों के सेट के साथ मेल खाता है। भाषा एनपी कक्षा एनपी में है; रेखांकन के आइसोमोर्फिज्म का प्रमाण पहले ग्राफ के कोने के क्रमांकन है, जो एक आइसोमोर्फिज्म को परिभाषित करता है। क्या जीआई कक्षा पी में है, एक खुला प्रश्न है। हम जीएनआई भाषा पर भी विचार करते हैं, जिसमें समान संख्याओं पर गैरिसोमोर्फिक ग्राफ़ के जोड़े होते हैं। यह जीएनआई भाषा के बारे में ज्ञात नहीं है कि क्या यह एनपी में निहित है, क्योंकि यह स्पष्ट नहीं है कि कैसे संक्षिप्त रूप से साबित किया जाए कि दो रेखांकन आइसोमोर्फिक नहीं हैं।
  
• HamPath भाषा पर विचार करें, जिसमें रेखांकन होता है जिसमें एक हैमिल्टन मार्ग है, अर्थात ऐसा मार्ग जो प्रत्येक शिखर से एक बार गुजरता है। यह भाषा कक्षा एनपी में निहित है, क्योंकि पथ का उपयोग खुद पथ के अस्तित्व के प्रमाण के रूप में किया जा सकता है। इस भाषा के बारे में यह ज्ञात नहीं है कि यह कक्षा P में निहित है, लेकिन यह ज्ञात है कि यह NP- पूर्ण है। उत्तरार्द्ध, विशेष रूप से, इसका मतलब है कि हमपथ पी में झूठ नहीं बोलता है अगर पी। एनपी। हम्पथ का जोड़ कई ग्राफों के साथ मेल खाता है जिसमें कोई हैमिल्टन मार्ग नहीं है। क्या हमपा का पूरक वर्ग एनपी अज्ञात है।
  

इंटरएक्टिव साक्ष्य

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

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

इंटरएक्टिव प्रूफ के एक उदाहरण पर विचार करें: एक प्रोग्राम है जो ग्राफ आइसोमॉर्फिज़्म की समस्या को हल करता है। इस मामले में जब ग्राफ समसामयिक होते हैं, तो प्रोग्राम एक आइसोमोर्फिज्म को परिभाषित करने वाले क्रमचय को जारी करके अपने उत्तर की शुद्धता साबित कर सकता है। हम दिखाते हैं कि कैसे एक संवाद में साबित करना है कि रेखांकन आइसोमॉर्फिक नहीं है। यदि उपयोगकर्ता G ₀ और G ₁ को आइसोमोर्फ़िक कहते हैं और उन्हें गैर-आइसोमॉर्फ़िक है तो जवाब मिलता है कि उपयोगकर्ता से पूछें। उसके बाद, उपयोगकर्ता एक सिक्का फेंकता है (सेट {0,1} सेट से एक यादृच्छिक तत्व का चयन करता है) और एन-एलिमेंट सेट के यादृच्छिक क्रमांकन का चयन करता है (इस मामले में, सभी क्रमपरिवर्तन को समान रूप से संभावित माना जाता है) th। और वह प्रोग्राम से पूछता है कि क्या ग्राफ जी ₀ , G (जी _आई ) आइसोमॉर्फिक हैं। यदि मैं = 0 है, तो प्रोग्राम एक उत्तर की अपेक्षा करता है कि रेखांकन समसामयिक हैं, और यदि मैं = 1 है, तो कार्यक्रम यह अपेक्षा करता है कि रेखांकन समधर्मी है। यदि ग्राफ जी ₀ और जी ₁ वास्तव में गैर-आइसोमॉर्फिक थे, तो कार्यक्रम आसानी से इस प्रश्न का सही उत्तर देगा। लेकिन यदि जी ₀ और जी ₁ आइसोमॉर्फिक थे, तो समान संभावना वाले ग्राफ G (जी _आई ) या तो जी _{0 के} क्रमचय या जी _{1 के} क्रमपरिवर्तन हो सकते हैं, इसलिए, कार्यक्रम 1/2 से अधिक नहीं की संभावना के साथ अपेक्षित उत्तर देगा। एल्गोरिथ्म को बार-बार दोहराकर और यह निर्णय लेते हुए कि एल्गोरिदम सही ढंग से काम करता है, तो त्रुटि की संभावना को कम किया जा सकता है, यदि प्रत्येक उत्तर में सही उत्तर दिया गया हो; इस मामले में त्रुटि संभावना 1/2 ⁿ से अधिक नहीं है।

उदाहरण में सिर्फ जांच की गई है, सबूत प्रोवर (प्रोग्राम) और वेरिफ़ायर (उपयोगकर्ता) के बीच एक संवाद है, जबकि प्रोवर बहुत जटिल हो सकता है, और सत्यापनकर्ता केवल साधारण चीजें कर सकता है (बहुपद समय गणना करें)। यदि तत्व x theL है, तो प्रोवर को प्रायिकता 1 के साथ, इस के सत्यापनकर्ता को आश्वस्त करना चाहिए, और यदि x theL है, तो सत्यापनकर्ता को ऐसे प्रमाण को 1/10 से अधिक नहीं की संभावना के साथ स्वीकार करना चाहिए। शमीर के प्रमेय में कहा गया है कि छोटे संवादों के साथ इस तरह के इंटरैक्टिव प्रूफ सिस्टम सभी एल भाषाओं के लिए मौजूद हैं, जिनके लिए मान्यता एल्गोरिदम हैं जो बहुपद स्मृति का उपयोग करते हैं। विशेष रूप से, बहुपद समय में यह साबित किया जा सकता है कि ग्राफ में कोई हैमिल्टन मार्ग नहीं है।

शून्य-प्रकटीकरण साक्ष्य

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

एक उदाहरण पर विचार करें: कुछ कंपनी ऐसे प्रोग्राम लिखती हैं जो ग्राफ़िक्स के आइसोमोर्फिज़्म की समस्या को जल्दी से हल कर देते हैं, लेकिन इस प्रोग्राम का फ़्री वर्ज़न बस यह कहता है कि ग्राफ़ के आइसोमॉर्फ़िक होने पर मामले में कोई परमीशन दिए बिना ग्राफ़ इस्मोर्फिक है या नहीं। क्रमचय प्राप्त करने के लिए, आपको प्रोग्राम का एक भुगतान किया गया संस्करण खरीदना होगा। लेकिन इस बीच, डेवलपर्स चाहते हैं कि उपयोगकर्ता यह सत्यापित करने में सक्षम हो कि ग्राफ़ वास्तव में आइसोमोर्फिक हैं, लेकिन इतना है कि यह जानकारी उपयोगकर्ता को अपने आप में इस समरूपता को खोजने में मदद नहीं करती है। यह निम्नानुसार किया जा सकता है: यदि ग्राफ जी ₀ और जी ₁ आइसोमोर्फिक हैं, तो हम एक यादृच्छिक क्रमांकन perm चुन सकते हैं और ग्राफ जी ₂ = π (जी ₁ ) दे सकते हैं और उपयोगकर्ता को यह तय करने की पेशकश कर सकते हैं कि वह किस ग्राफ के समसामयिकता को जी ₀ और जी ₂ या जी ₂ प्राप्त करना चाहता है। ₁ और जी ₂ । कार्यक्रम इन अनुरोधों में से एक का जवाब देगा। यदि प्रोग्राम isomorphism को जानता है, तो वह आसानी से उपयोगकर्ता के अनुरोध का जवाब देगा; यदि कोई isomorphism नहीं है, तो कम से कम उपयोगकर्ता के अनुरोध के किसी एक संस्करण के लिए यह काम नहीं करेगा। और यदि उपयोगकर्ता किसी क्वेरी को बेतरतीब ढंग से चुनता है, तो संभावना है कि उपयोगकर्ता द्वारा चुने गए विकल्पों के बीच एक समरूपता 1/2 से अधिक नहीं है। इस प्रक्रिया को दोहराकर त्रुटि को कम किया जा सकता है: एक नया क्रमचय चुनना और एक नया विकल्प चुनने के लिए उपयोगकर्ता को संकेत देना।

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

संभवतया सत्यापन योग्य साक्ष्य

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

आइए हम नॉनसोमोर्फिक जीएनआई ग्राफ़ की जोड़ी की भाषा के लिए एक उदाहरण दें। हमारे उदाहरण में, प्रमाण घातीय लंबाई का होगा, अर्थात् n शीर्ष पर रेखांकन के लिए प्रमाण का आकार 2 ^{n (n-1) / 2 होगा} , यहाँ n (n-1) / 2 किनारों की अधिकतम संख्या है जो n पर एक ग्राफ हो सकता है सबसे ऊपर है। ग्राफ ₀ और जी ₁ की एक जोड़ी के गैरिसोमोर्फिज्म का प्रमाण लंबाई 2 ^{एन (एन -1) / 2} का एक सा स्ट्रिंग डब्ल्यू है, जो कि एन वर्टिकल में सभी अलग-अलग रेखांकन द्वारा अनुक्रमित होता है। ग्राफ H के समान स्ट्रिंग W का बिट शून्य है यदि H, G ₀ से समद्विबाहु है, तो यदि ग्राफ G _{1 के} लिए आइसोमॉर्फ़िक है, और यदि ग्राफ़ H या ₀ या G ₁ से कोई भी समान नहीं है, तो ग्राफ़ कुछ के बराबर है। यह आंकड़ा तीन रेखाओं में दो गैर-विसंगति रेखांकन के लिए इस तरह की एक पंक्ति w का उदाहरण दिखाता है:



इस तरह के प्रमाण का सत्यापन एक संवादात्मक प्रमाण के समान है: आपको एक सिक्का फेंकना होगा ({0,1} से यादृच्छिक i), यादृच्छिक क्रमपरिवर्तन proof और ग्राफ σ (G _i ) के अनुरूप प्रमाण को देखें, यदि मैं इसके साथ मेल खाता हूं, तो इस प्रमाण को स्वीकार करें यदि यह मेरे साथ मेल नहीं खाता है, तो अस्वीकार करें। इस मामले में जब ग्राफ जी ₀ और जी ₁ गैर _- समरूप हैं, तो इस तरह के प्रमाण को स्वीकार किया जाएगा।यदि ग्राफ़ G ₀ और G ₁ समरूप है, तो समान संभावना वाले ग्राफ G (G _i ) G ₀ और G ₁ का क्रमचय हो सकता है , इसलिए, प्रमाण को 1/2 की संभावना के साथ स्वीकार किया जाएगा। स्वतंत्र यादृच्छिक विकल्पों i और we के लिए 10 बार इस परीक्षण को दोहराकर, हम त्रुटि की संभावना को 1/1024 तक कम कर सकते हैं।

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

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

संदर्भ

साहित्य जिसमें लेख में उल्लिखित सभी आरोपों के कठोर सूत्र और साक्ष्य मिल सकते हैं:

• एस। अरोड़ा, बी। बराक, कम्प्यूटेशनल जटिलता: एक आधुनिक दृष्टिकोण
• ओ। गोदरिच , द फ़ाउंडेशन ऑफ़ क्रिप्टोगटैफी
• यू। वी। मटियासेविच, दसवीं हिल्बर्ट समस्या। - एम ।: नुका, 1993 ।-- आईएसबीएन 502014326X
• एन.के. वीरेशचैजिन, क्रिप्टोग्राफी की जटिल सैद्धांतिक समस्याएं , व्याख्यान नोट्स
• डीएम इटिऑक्सन, सैद्धांतिक कंप्यूटर विज्ञान पर सर्वेक्षण पाठ्यक्रम , व्याख्यान नोट्स

सैद्धांतिक कंप्यूटर विज्ञान में रुचि रखने वालों को अकादमिक विश्वविद्यालय के मास्टर कार्यक्रम पर ध्यान देने की सलाह दी जाती है ।