इंटरैक्टिव प्रमाण प्रणाली: Difference between revisions

From Vigyanwiki
(Created page with "{{distinguish|Proof assistant}} File:Interactive proof (complexity).svg|thumb|300px|एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल क...")
 
No edit summary
Line 1: Line 1:
{{distinguish|Proof assistant}}
{{distinguish|प्रमाण सहायक}}
[[File:Interactive proof (complexity).svg|thumb|300px|एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक इंटरैक्टिव प्रूफ सिस्टम एक [[अमूर्त मशीन]] है जो दो पक्षों के बीच संदेशों के आदान-प्रदान के रूप में [[गणना]] करती है: एक ''प्रोवर'' और एक ''सत्यापनकर्ता''। पार्टियां यह सुनिश्चित करने के लिए संदेशों का आदान-प्रदान करके बातचीत करती हैं कि दी गई [[स्ट्रिंग (कंप्यूटर विज्ञान)]] [[औपचारिक भाषा]] से संबंधित है या नहीं। सत्यापनकर्ता के पास असीमित कम्प्यूटेशनल संसाधन होते हैं लेकिन उस पर भरोसा नहीं किया जा सकता है, जबकि सत्यापनकर्ता के पास सीमित गणना शक्ति होती है लेकिन यह माना जाता है कि वह हमेशा ईमानदार रहता है। सत्यापनकर्ता और सत्यापनकर्ता के बीच संदेश तब तक भेजे जाते हैं जब तक कि सत्यापनकर्ता के पास समस्या का उत्तर न हो और वह आश्वस्त न हो जाए कि यह सही है।
[[File:Interactive proof (complexity).svg|thumb|300px|एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।]][[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी]] में, इंटरैक्टिव प्रूफ सिस्टम एक [[अमूर्त मशीन|एब्स्ट्रैक्ट मशीन]] है जो दो पक्षों के बीच मैसेज के आदान-प्रदान के रूप में [[गणना]] करती है: एक प्रूवर और एक वेरिफायर। पार्टियां यह सुनिश्चित करने के लिए मैसेज का आदान-प्रदान करके इंटरैक्ट करती हैं कि दी गई [[स्ट्रिंग (कंप्यूटर विज्ञान)]] [[औपचारिक भाषा|फॉर्मल लैंग्वेज]] से संबंधित है या नहीं। वेरिफायर के पास असीमित कम्प्यूटेशनल रिसोर्स होते हैं लेकिन उस पर विश्‍वास नहीं किया जा सकता है, जबकि वेरिफायर के पास बॉउंडेड कम्प्यूटेशन पावर होती है लेकिन यह माना जाता है कि वह हमेशा ऑनेस्ट रहता है। वेरिफायर और वेरिफायर के बीच मैसेज तब तक भेजे जाते हैं जब तक कि वेरिफायर के पास प्रॉब्लम का उत्तर न हो और वह आश्वस्त न हो जाए कि यह सही है।


सभी इंटरैक्टिव प्रूफ सिस्टम की दो आवश्यकताएँ होती हैं:
सभी इंटरैक्टिव प्रूफ सिस्टम की दो आवश्यकताएँ होती हैं:
* पूर्णता: यदि कथन सत्य है, तो ईमानदार सत्यापनकर्ता (अर्थात प्रोटोकॉल का ठीक से पालन करने वाला) ईमानदार सत्यापनकर्ता को यह विश्वास दिला सकता है कि यह वास्तव में सत्य है।
* कम्प्लीटनेस: यदि कथन सत्य है, तो ऑनेस्ट वेरिफायर (अर्थात प्रोटोकॉल का ठीक से पालन करने वाला) ऑनेस्ट वेरिफायर को कन्विंस कर सकता है कि यह वास्तव में सत्य है।
* सुदृढ़ता: यदि कथन गलत है, तो कोई भी सूचक, भले ही वह प्रोटोकॉल का पालन न करता हो, ईमानदार सत्यापनकर्ता को यह विश्वास नहीं दिला सकता कि यह सत्य है, कुछ छोटी [[संभावना]]ओं को छोड़कर।
* साउंडनेस: यदि कथन गलत है, तो कोई भी प्रूवर, भले ही वह प्रोटोकॉल का पालन न करता हो, ऑनेस्ट वेरिफायर को यह कन्विंस नहीं कर सकता कि यह सत्य है, कुछ छोटी प्रोबेबिलिटी को छोड़कर।


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


== पृष्ठभूमि ==
== पृष्ठभूमि ==


प्रत्येक इंटरैक्टिव प्रूफ सिस्टम स्ट्रिंग्स की एक औपचारिक भाषा को परिभाषित करता है <math>L</math>. प्रमाण प्रणाली की सुदृढ़ता उस संपत्ति को संदर्भित करती है जिसे कोई भी नीति सत्यापनकर्ता गलत कथन के लिए स्वीकार नहीं कर सकता है <math>y \not\in L</math> कुछ छोटी संभावनाओं को छोड़कर। इस संभावना की ऊपरी सीमा को प्रूफ सिस्टम की सुदृढ़ता त्रुटि के रूप में जाना जाता है। अधिक औपचारिक रूप से, प्रत्येक कहावत के लिए <math>(\tilde{\mathcal{P}})</math>, और हर <math>y \not\in L</math>:
प्रत्येक इंटरैक्टिव प्रूफ सिस्टम स्ट्रिंग्स की एक फॉर्मल लैंग्वेज <math>L</math> को परिभाषित करता है। प्रूफ सिस्टम की साउंडनेस उस प्रॉपर्टी को संदर्भित करती है जिसे कोई भी नीति वेरिफायर रॉंग स्टेटमेंट <math>y \not\in L</math> के लिए कुछ छोटी संभावनाओं को छोड़कर एक्सेप्ट नहीं कर सकता है। इस प्रोबेबिलिटी की ऊपरी सीमा को प्रूफ सिस्टम की साउंडनेस एरर के रूप में जाना जाता है। अधिक औपचारिक रूप से, प्रत्येक <math>(\tilde{\mathcal{P}})</math> प्रोवेर और हर <math>y \not\in L</math> के लिए :


: <math>\Pr[(\perp,(\text{accept}))\gets (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)] < \epsilon.</math>
: <math>\Pr[(\perp,(\text{accept}))\gets (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)] < \epsilon.</math>
कुछ के लिए <math> \epsilon \ll 1 </math>.
कुछ <math> \epsilon \ll 1 </math> के लिए ।
जब तक सुदृढ़ता त्रुटि सत्यापनकर्ता के संभावित चलने के समय के बहुपद अंश से बंधी होती है (यानी) <math>\epsilon\leq1/\mathrm{poly}(|y|)</math>), सुदृढ़ता को बढ़ाना हमेशा संभव होता है जब तक कि सत्यापनकर्ता के चलने के समय के सापेक्ष सुदृढ़ता त्रुटि [[नगण्य]] न हो जाए। यह प्रमाण को दोहराने और सभी प्रमाण सत्यापित होने पर ही स्वीकार करने से प्राप्त होता है। बाद <math>\ell</math> दोहराव, एक ध्वनि त्रुटि <math>\epsilon</math> तक कम कर दिया जाएगा <math>\epsilon^\ell</math>.<ref>{{citation|first=Oded|last=Goldreich|authorlink=Oded Goldreich|title=Zero-Knowledge twenty years after its invention|year=2002|id={{ECCC|2002|02|063}}}}.</ref>
 
जब तक साउंडनेस एरर वेरिफायर के संभावित रनिंग टाइम के बहुपद अंश से बंधी होती है (यानी) <math>\epsilon\leq1/\mathrm{poly}(|y|)</math>), साउंडनेस को बढ़ाना हमेशा संभव होता है जब तक कि वेरिफायर के रनिंग टाइम के सापेक्ष साउंडनेस एरर [[नगण्य|नेग्लिजिबल फंक्शन]] न हो जाए। यह प्रूफ को दोहराने और सभी प्रूफ वेरीफाई होने पर ही एक्सेप्ट करने से प्राप्त होता है। बाद <math>\ell</math> दोहराव, एक ध्वनि एरर <math>\epsilon</math> <math>\epsilon^\ell</math> तक कम कर दिया जाएगा। <ref>{{citation|first=Oded|last=Goldreich|authorlink=Oded Goldreich|title=Zero-Knowledge twenty years after its invention|year=2002|id={{ECCC|2002|02|063}}}}.</ref>
 




Line 21: Line 23:
=== एनपी ===
=== एनपी ===


जटिलता वर्ग [[एन[[पी (जटिलता)]]]] को एक बहुत ही सरल प्रमाण प्रणाली के रूप में देखा जा सकता है। इस प्रणाली में, सत्यापनकर्ता एक नियतात्मक, बहुपद-समय मशीन (एक पी (जटिलता) मशीन) है। प्रोटोकॉल है:
कम्प्लेक्सिटी क्लास [[एन[[पी (जटिलता)|पी (कम्प्लेक्सिटी)]]]] को एक बहुत ही सिंपल प्रूफ सिस्टम के रूप में देखा जा सकता है। इस सिस्टम में, वेरिफायर एक डिटर्मिनिस्टिक, पोलीनोमिअल-साइज (एक पी (कम्प्लेक्सिटी) मशीन) है। प्रोटोकॉल है:
* प्रोवर इनपुट को देखता है और अपनी असीमित शक्ति का उपयोग करके समाधान की गणना करता है और एक बहुपद-आकार प्रमाण प्रमाण पत्र लौटाता है।
* प्रूवर इनपुट को देखता है और अपनी अनलिमिटेड पावर का उपयोग करके समाधान की गणना करता है और एक पोलीनोमिअल-साइज प्रूफ सर्टिफिकेट लौटाता है।
* सत्यापनकर्ता सत्यापित करता है कि प्रमाणपत्र नियतात्मक बहुपद समय में वैध है। यदि यह वैध है, तो यह स्वीकार करता है; अन्यथा, यह अस्वीकार कर देता है।
* वेरिफायर वेरीफाई करता है कि सर्टिफिकेट डिटर्मिनिस्टिक बहुपद समय में वैलिड है। यदि यह वैलिड है, तो यह एक्सेप्ट करता है; अन्यथा, यह रिजेक्ट कर देता है।


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


=== आर्थर-मर्लिन और मर्लिन-आर्थर प्रोटोकॉल ===
=== आर्थर-मर्लिन और मर्लिन-आर्थर प्रोटोकॉल ===
{{main|Arthur–Merlin protocol}}
{{main|मर्लिन-आर्थर प्रोटोकॉल}}
यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 1985 तक नहीं था कि शोधकर्ताओं के दो स्वतंत्र समूहों द्वारा इंटरैक्शन के माध्यम से गणना की अवधारणा की कल्पना की गई थी (जटिलता सिद्धांत के संदर्भ में)। एक दृष्टिकोण, लास्ज़लो बाबाई द्वारा, जिन्होंने यादृच्छिकता के लिए ट्रेडिंग समूह सिद्धांत प्रकाशित किया,<ref>László Babai. [http://portal.acm.org/citation.cfm?id=22192 Trading group theory for randomness]. ''Proceedings of the Seventeenth Annual Symposium on the Theory of Computing'', ACM. 1985.</ref> आर्थर-मर्लिन ('एएम') वर्ग पदानुक्रम को परिभाषित किया। इस प्रस्तुति में, आर्थर (सत्यापनकर्ता) एक [[संभाव्य ट्यूरिंग मशीन]], बहुपद-समय मशीन है, जबकि मर्लिन (कहावतकर्ता) के पास असीमित संसाधन हैं।
 
यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 1985 तक नहीं था कि रिसर्चर के दो इंडिपेंडेंट ग्रुप द्वारा इंटरैक्शन के माध्यम से गणना की अवधारणा की कल्पना की गई थी (कम्प्लेक्सिटी थ्योरी के संदर्भ में)। एक दृष्टिकोण, लास्ज़लो बाबाई द्वारा, जिन्होंने "ट्रेडिंग ग्रुप थ्योरी फॉर रैंडमनेस" प्रकाशित किया, <ref>László Babai. [http://portal.acm.org/citation.cfm?id=22192 Trading group theory for randomness]. ''Proceedings of the Seventeenth Annual Symposium on the Theory of Computing'', ACM. 1985.</ref> आर्थर-मर्लिन ('एएम') क्लास हायरार्की को परिभाषित किया। इस प्रस्तुति में, आर्थर (वेरिफायर) एक [[संभाव्य ट्यूरिंग मशीन|प्रोबबिलिस्टिक ट्यूरिंग मशीन]], पोलीनोमिअल-टाइम मशीन है, जबकि मर्लिन (वेरीफायर) के पास अनबाउंडेड रिसोर्स हैं।
 
विशेष रूप से क्लास 'एमए' उपरोक्त एनपी इंटरैक्शन का एक सिंपल जनरलाइज़ेशन है जिसमें वेरिफायर डिटर्मिनिस्टिक के स्थान पर डेटर्मीनिस्टिक है। साथ ही, यह अपेक्षा करने के स्थान पर कि वेरिफायर हमेशा वैलिड सर्टिफिकेट एक्सेप्ट करें और इनवैलिड सर्टिफिकेट रिजेक्ट करें, यह अधिक लेनिएंट है:
* 'कम्प्लीटनेस:' यदि स्ट्रिंग लैंग्वेज में है, तो प्रूवर को एक प्रूफ सर्टिफिकेट देने में सक्षम होना चाहिए, जिसे वेरिफायर कम से कम 2/3 प्रोबेबिलिटी के साथ एक्सेप्ट करेगा (वेरिफायर के रैंडम चॉइस के आधार पर)।
* 'साउंडनेस:' यदि स्ट्रिंग लैंग्वेज में नहीं है, तो कोई भी प्रूवर, चाहे वह कितनी भी मालिशियस क्यों न हो, वेरिफायर को 1/3 से अधिक प्रोबेबिलिटी वाली स्ट्रिंग को एक्सेप्ट करने के लिए मनाने में सक्षम नहीं होगी।


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


यह मशीन सामान्य एनपी [[इंटरेक्शन प्रोटोकॉल]] की तुलना में संभावित रूप से अधिक शक्तिशाली है, और प्रमाणपत्र सत्यापित करने के लिए कम व्यावहारिक नहीं हैं, क्योंकि 'बीपीपी' एल्गोरिदम को अमूर्त व्यावहारिक गणना के रूप में माना जाता है ([[परिबद्ध-त्रुटि संभाव्य बहुपद]] देखें)।
=== पब्लिक कॉइन प्रोटोकॉल बनाम प्राइवेट कॉइन प्रोटोकॉल ===


=== सार्वजनिक सिक्का प्रोटोकॉल बनाम निजी सिक्का प्रोटोकॉल ===
पब्लिक कॉइन प्रोटोकॉल में, वेरिफायर द्वारा चुने गए  रैंडम चॉइस को पब्लिक किया जाता है। वे प्राइवेट कॉइन प्रोटोकॉल में प्राइवेट रहते हैं।


सार्वजनिक सिक्का प्रोटोकॉल में, सत्यापनकर्ता द्वारा चुने गए यादृच्छिक विकल्पों को सार्वजनिक किया जाता है। वे निजी सिक्का प्रोटोकॉल में निजी रहते हैं।
उसी सम्मेलन में जहां बाबई ने 'एमए' के ​​लिए अपनी प्रूफ सिस्टम को परिभाषित किया, [[शफ़ी गोल्डवेसर]], [[सिल्वियो मिकाली]] और [[ चार्ल्स रैकॉफ़ |चार्ल्स रैकॉफ़]] <ref>{{Cite journal | last1=Goldwasser | first1=S. | last2=Micali | first2=S. | last3=Rackoff | first3=C. | title=इंटरैक्टिव प्रूफ सिस्टम की ज्ञान जटिलता| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf | year=1989 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=18 | issue=1 | pages=186–208 | doi=10.1137/0218012}} [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract]</ref> इंटरैक्टिव प्रूफ सिस्टम आईपी [''एफ''(''एन'')] को परिभाषित करने वाला एक पेपर पब्लिश किया। इसमें एमए प्रोटोकॉल के समान मशीनें हैं, सिवाय इसके कि एन आकार के इनपुट के लिए एफ(एन) राउंड की अनुमति है। प्रत्येक दौर में, वेरिफायर गणना करता है और प्रूवर को एक मैसेज भेजता है, और प्रूवर गणना करता है और वेरिफायर को जानकारी वापस भेजता है। अंत में वेरिफायर को अपना निर्णय लेना होगा। उदाहरण के लिए, एक आईपी[3] प्रोटोकॉल में, अनुक्रम वीपीवीपीवीपीवी होगा, जहां वी एक वेरिफायर टर्न है और पी एक प्रूवर टर्न है।


उसी सम्मेलन में जहां बाबई ने 'एमए' के ​​लिए अपनी प्रमाण प्रणाली को परिभाषित किया, [[शफ़ी गोल्डवेसर]], [[सिल्वियो मिकाली]] और [[ चार्ल्स रैकॉफ़ ]]<ref>{{Cite journal | last1=Goldwasser | first1=S. | last2=Micali | first2=S. | last3=Rackoff | first3=C. | title=इंटरैक्टिव प्रूफ सिस्टम की ज्ञान जटिलता| url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf | year=1989 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=18 | issue=1 | pages=186–208 | doi=10.1137/0218012}} [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract]</ref> इंटरैक्टिव प्रूफ सिस्टम आईपी[''एफ''(''एन'')] को परिभाषित करने वाला एक पेपर प्रकाशित किया। इसमें एमए प्रोटोकॉल के समान मशीनें हैं, सिवाय इसके कि ''एन'' आकार के इनपुट के लिए ''एफ''(''एन'') ''राउंड'' की अनुमति है। प्रत्येक दौर में, सत्यापनकर्ता गणना करता है और प्रूवर को एक संदेश भेजता है, और प्रूवर गणना करता है और सत्यापनकर्ता को जानकारी वापस भेजता है। अंत में सत्यापनकर्ता को अपना निर्णय लेना होगा। उदाहरण के लिए, एक आईपी[3] प्रोटोकॉल में, अनुक्रम वीपीवीपीवीपीवी होगा, जहां वी एक सत्यापनकर्ता टर्न है और पी एक प्रोवर टर्न है।
आर्थर-मर्लिन प्रोटोकॉल में, बाबई ने एक समान वर्ग AM[''f''(''n'')] को परिभाषित किया, जो ''f''(''n'') राउंड की अनुमति देता था, लेकिन उन्होंने एक अतिरिक्त कंडीशन रखी कि मशीन: वेरिफायर को अपनी गणना में उपयोग किए जाने वाले सभी  रैंडम बिट्स को प्रूवर को दिखाना होगा। इसका परिणाम यह होता है कि वेरिफायर प्रूवर से कुछ भी नहीं छिपा सकता है, क्योंकि प्रूवर इतना शक्तिशाली है कि वेरिफायर जो कुछ भी करता है उसका अनुकरण कर सकता है यदि उसे पता हो कि उसने कौन से यादृच्छिक बिट्स का उपयोग किया है। इसे पब्लिक कॉइन प्रोटोकॉल कहा जाता है, क्योंकि यादृच्छिक बिट्स (कॉइन फ्लिप) दोनों मशीनों पर दिखाई देते हैं। इसके विपरीत आईपी दृष्टिकोण को प्राइवेट कॉइन प्रोटोकॉल कहा जाता है।


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


सार्वजनिक सिक्कों के साथ मुख्य समस्या यह है कि यदि सूचक दुर्भावनापूर्वक सत्यापनकर्ता को एक स्ट्रिंग स्वीकार करने के लिए राजी करना चाहता है जो भाषा में नहीं है, तो ऐसा लगता है कि सत्यापनकर्ता अपनी योजनाओं को विफल करने में सक्षम हो सकता है यदि वह अपनी आंतरिक स्थिति को इससे छिपा सकता है। आईपी ​​प्रूफ सिस्टम को परिभाषित करने में यह एक प्राथमिक प्रेरणा थी।
1986 में, गोल्डवेसर और [[माइकल सिप्सर]] <ref>Shafi Goldwasser and Michael Sipser. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf Private coins versus public coins in interactive proof systems]. ''Proceedings of ACM STOC'86'', pp. 58–68. 1986.</ref> दिखाया गया है, शायद आश्चर्यजनक रूप से, कि प्रूवर से कॉइन के फ्लिप को छिपाने की वेरिफायर की क्षमता आखिरकार कुछ भी अच्छा नहीं करती है, जिसमें केवल दो और राउंड के साथ एक आर्थर-मर्लिन पब्लिक कॉइन प्रोटोकॉल सभी समान भाषाओं को पहचान सकता है। नतीजा यह है कि पब्लिक-कॉइन और प्राइवेट-कॉइन प्रोटोकॉल लगभग बराबर हैं। वास्तव में, जैसा कि बाबई ने 1988 में दिखाया था, सभी स्थिरांक ''k'' के लिए AM[''k'']=AM, इसलिए IP[''k''] का AM पर कोई लाभ नहीं है। <ref>László Babai and [[Shlomo Moran]]. [http://portal.acm.org/citation.cfm?id=49987 Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes]. ''Journal of Computer and System Sciences'', 36: p.254–276. 1988.</ref>
 
इन क्लासेज की पावर को प्रदर्शित करने के लिए, [[ग्राफ समरूपता समस्या|ग्राफ इसोमोर्फिसम प्रॉब्लम]] पर विचार करें, यह निर्धारित करने की प्रॉब्लम कि क्या एक ग्राफ के वर्टाइसेस को परम्यूट करना संभव है ताकि यह दूसरे ग्राफ के समान हो। यह प्रॉब्लम एनपी में है, क्योंकि प्रूफ सर्टिफिकेट परम्यूटेशन है जो ग्राफ़ को समान बनाता है। यह पता चला है कि ग्राफ इसोमोर्फिसम प्रॉब्लम का [[पूरक (जटिलता)|पूरक (कम्प्लेक्सिटी)]], एक सह-एनपी प्रॉब्लम जिसे एनपी में नहीं जाना जाता है, में एक एएम एल्गोरिदम है और इसे देखने का सबसे अच्छा तरीका एक प्राइवेट कॉइन एल्गोरिदम के माध्यम से है। <ref name="O. Goldreich, S. Micali 1991">O. Goldreich, S. Micali, A. Wigderson. [http://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690–728. July 1991.</ref>


1986 में, गोल्डवेसर और [[माइकल सिप्सर]]<ref>Shafi Goldwasser and Michael Sipser. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf Private coins versus public coins in interactive proof systems]. ''Proceedings of ACM STOC'86'', pp. 58–68. 1986.</ref> दिखाया गया है, शायद आश्चर्यजनक रूप से, कि कहावत से सिक्के के फ्लिप को छिपाने की सत्यापनकर्ता की क्षमता आखिरकार कुछ भी अच्छा नहीं करती है, जिसमें केवल दो और राउंड के साथ एक आर्थर-मर्लिन सार्वजनिक सिक्का प्रोटोकॉल सभी समान भाषाओं को पहचान सकता है। नतीजा यह है कि सार्वजनिक-सिक्का और निजी-सिक्का प्रोटोकॉल लगभग बराबर हैं। वास्तव में, जैसा कि बाबई ने 1988 में दिखाया था, सभी स्थिरांक ''k'' के लिए AM[''k'']=AM, इसलिए IP[''k''] का AM पर कोई लाभ नहीं है।<ref>László Babai and [[Shlomo Moran]]. [http://portal.acm.org/citation.cfm?id=49987 Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes]. ''Journal of Computer and System Sciences'', 36: p.254–276. 1988.</ref>
इन वर्गों की शक्ति को प्रदर्शित करने के लिए, [[ग्राफ समरूपता समस्या]] पर विचार करें, यह निर्धारित करने की समस्या कि क्या एक ग्राफ के शीर्षों को क्रमबद्ध करना संभव है ताकि यह दूसरे ग्राफ के समान हो। यह समस्या एनपी में है, क्योंकि प्रमाण प्रमाणपत्र क्रमपरिवर्तन है जो ग्राफ़ को समान बनाता है। यह पता चला है कि
ग्राफ समरूपता समस्या का [[पूरक (जटिलता)]], एक सह-एनपी समस्या जिसे एनपी में नहीं जाना जाता है, में एक एएम एल्गोरिदम है और इसे देखने का सबसे अच्छा तरीका एक निजी सिक्के एल्गोरिदम के माध्यम से है।<ref name="O. Goldreich, S. Micali 1991">O. Goldreich, S. Micali, A. Wigderson. [http://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690–728. July 1991.</ref>




=== आईपी ===
=== आईपी ===
{{main|IP (complexity)}}
{{main|आईपी (कम्प्लेक्सिटी)}}
निजी सिक्के मददगार नहीं हो सकते हैं, लेकिन बातचीत के अधिक दौर मददगार होते हैं। यदि हम संभाव्य सत्यापनकर्ता मशीन और सर्व-शक्तिशाली प्रोवर को बहुपद संख्या में राउंड के लिए बातचीत करने की अनुमति देते हैं, तो हमें समस्याओं का वर्ग मिलता है जिसे आईपी कहा जाता है।
 
1992 में, [[आदि शमीर]] ने जटिलता सिद्धांत के केंद्रीय परिणामों में से एक में खुलासा किया कि आईपी [[PSPACE]] के बराबर है, बहुपद अंतरिक्ष में एक साधारण [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल की जाने वाली समस्याओं का वर्ग।<ref>Adi Shamir. [http://portal.acm.org/citation.cfm?doid=146585.146609 IP = PSPACE]. ''Journal of the ACM'', volume 39, issue 4, p.869–877. October 1992.</ref>
'''प्राइवेट कॉइन हेल्पफुल न'''हीं हो सकते हैं, लेकिन इंटरेक्शन के अधिक दौर हेल्पफुल होते हैं। यदि हम संभाव्य वेरिफायर मशीन और सर्व-शक्तिशाली प्रूवर को बहुपद संख्या में राउंड के लिए इंटरेक्शन करने की अनुमति देते हैं, तो हमें समस्याओं का वर्ग मिलता है जिसे आईपी कहा जाता है।
1992 में, [[आदि शमीर]] ने कम्प्लेक्सिटी थ्योरी के केंद्रीय परिणामों में से एक में खुलासा किया कि आईपी [[PSPACE]] के बराबर है, बहुपद अंतरिक्ष में एक साधारण [[नियतात्मक ट्यूरिंग मशीन|डिटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल की जाने वाली समस्याओं का वर्ग।<ref>Adi Shamir. [http://portal.acm.org/citation.cfm?doid=146585.146609 IP = PSPACE]. ''Journal of the ACM'', volume 39, issue 4, p.869–877. October 1992.</ref>




=== क्यूआईपी ===
=== क्यूआईपी ===
{{main|QIP (complexity)}}
{{main|QIP (complexity)}}
यदि हम सिस्टम के तत्वों को [[क्वांटम गणना]] का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित जटिलता वर्ग को क्यूआईपी कहा जाता है।<ref>{{cite arXiv|eprint=1012.4427v2|author1=Tsuyoshi Ito|author2=Hirotada Kobayashi|author3=John Watrous|title=कमजोर त्रुटि सीमाओं के साथ क्वांटम इंटरैक्टिव प्रमाण|class=quant-ph|year=2010}}</ref> परिणामों की एक श्रृंखला 2010 में QIP = PSPACE की सफलता में परिणत हुई।<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | title=STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing | publisher=ACM | isbn=978-1-4503-0050-6 | year=2010 | chapter=QIP = PSPACE | pages=573–582}}</ref><ref>{{Cite journal | last1 = Aaronson | first1 = S. | doi = 10.1145/1859204.1859230 | title = QIP = PSPACE breakthrough | journal = Communications of the ACM | volume = 53 | issue = 12 | pages = 101 | year = 2010 | s2cid = 34380788 }}</ref>
यदि हम सिस्टम के तत्वों को [[क्वांटम गणना]] का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित कम्प्लेक्सिटी वर्ग को क्यूआईपी कहा जाता है।<ref>{{cite arXiv|eprint=1012.4427v2|author1=Tsuyoshi Ito|author2=Hirotada Kobayashi|author3=John Watrous|title=कमजोर त्रुटि सीमाओं के साथ क्वांटम इंटरैक्टिव प्रमाण|class=quant-ph|year=2010}}</ref> परिणामों की एक श्रृंखला 2010 में QIP = PSPACE की सफलता में परिणत हुई।<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | title=STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing | publisher=ACM | isbn=978-1-4503-0050-6 | year=2010 | chapter=QIP = PSPACE | pages=573–582}}</ref><ref>{{Cite journal | last1 = Aaronson | first1 = S. | doi = 10.1145/1859204.1859230 | title = QIP = PSPACE breakthrough | journal = Communications of the ACM | volume = 53 | issue = 12 | pages = 101 | year = 2010 | s2cid = 34380788 }}</ref>




=== शून्य ज्ञान ===
=== शून्य ज्ञान ===
{{main|Zero-knowledge proof}}
{{main|Zero-knowledge proof}}
न केवल इंटरैक्टिव प्रूफ सिस्टम उन समस्याओं को हल कर सकते हैं जिन पर एनपी में विश्वास नहीं किया जाता है, बल्कि एक-तरफ़ा कार्यों के अस्तित्व के बारे में धारणाओं के तहत, एक प्रोवर सत्यापनकर्ता को समाधान के बारे में जानकारी दिए बिना समाधान के बारे में आश्वस्त कर सकता है। यह तब महत्वपूर्ण है जब सत्यापनकर्ता पर पूर्ण समाधान पर भरोसा नहीं किया जा सकता है। पहले तो यह असंभव लगता है कि सत्यापनकर्ता आश्वस्त हो सके कि कोई समाधान है जब सत्यापनकर्ता ने प्रमाणपत्र नहीं देखा है, लेकिन ऐसे प्रमाण, जिन्हें [[शून्य-ज्ञान प्रमाण]] के रूप में जाना जाता है, वास्तव में एनपी में सभी समस्याओं के लिए मौजूद माने जाते हैं और मूल्यवान हैं [[क्रिप्टोग्राफी]]. विशिष्ट संख्या सैद्धांतिक भाषाओं के लिए गोल्डवेसर, मिकाली और रैकॉफ द्वारा आईपी पर मूल 1985 पेपर में शून्य-ज्ञान प्रमाणों का पहली बार उल्लेख किया गया था। हालाँकि उनकी शक्ति की सीमा [[ओडेड गोल्डरेइच]], सिल्वियो मिकाली और [[एवी विग्डर्सन]] द्वारा दिखाई गई थी।<ref name="O. Goldreich, S. Micali 1991"/>संपूर्ण एनपी के लिए, और इसे सबसे पहले [[रसेल इम्पाग्लिआज़ो]] और [[मोती युंग]] द्वारा सभी आईपी तक विस्तारित किया गया था।<ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [https://link.springer.com/chapter/10.1007%2F3-540-48184-2_4]</ref>
न केवल इंटरैक्टिव प्रूफ सिस्टम उन समस्याओं को हल कर सकते हैं जिन पर एनपी में विश्वास नहीं किया जाता है, बल्कि एक-तरफ़ा कार्यों के अस्तित्व के बारे में धारणाओं के तहत, एक प्रूवर वेरिफायर को समाधान के बारे में जानकारी दिए बिना समाधान के बारे में आश्वस्त कर सकता है। यह तब महत्वपूर्ण है जब वेरिफायर पर पूर्ण समाधान पर भरोसा नहीं किया जा सकता है। पहले तो यह असंभव लगता है कि वेरिफायर आश्वस्त हो सके कि कोई समाधान है जब वेरिफायर ने सर्टिफिकेट नहीं देखा है, लेकिन ऐसे प्रूफ, जिन्हें [[शून्य-ज्ञान प्रमाण|शून्य-ज्ञान प्रूफ]] के रूप में जाना जाता है, वास्तव में एनपी में सभी समस्याओं के लिए उपस्थित माने जाते हैं और मूल्यवान हैं [[क्रिप्टोग्राफी]]. विशिष्ट संख्या सैद्धांतिक भाषाओं के लिए गोल्डवेसर, मिकाली और रैकॉफ द्वारा आईपी पर मूल 1985 पेपर में शून्य-ज्ञान प्रमाणों का पहली बार उल्लेख किया गया था। हालाँकि उनकी शक्ति की सीमा [[ओडेड गोल्डरेइच]], सिल्वियो मिकाली और [[एवी विग्डर्सन]] द्वारा दिखाई गई थी।<ref name="O. Goldreich, S. Micali 1991"/>संपूर्ण एनपी के लिए, और इसे सबसे पहले [[रसेल इम्पाग्लिआज़ो]] और [[मोती युंग]] द्वारा सभी आईपी तक विस्तारित किया गया था।<ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [https://link.springer.com/chapter/10.1007%2F3-540-48184-2_4]</ref>




=== एमआईपी ===
=== एमआईपी ===
आईपी ​​के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि सत्यापनकर्ता को अधिक शक्तिशाली और इतना अव्यवहारिक बनाए बिना इसे और अधिक शक्तिशाली नहीं बनाया जा सकता है। गोल्डवेसर एट अल. अपने 1988 के मल्टी प्रोवर इंटरैक्टिव प्रूफ़्स में इस पर काबू पा लिया: अट्रैक्टिविटी धारणाओं को कैसे दूर करें, जो एमआईपी नामक आईपी के एक प्रकार को परिभाषित करता है जिसमें ''दो'' स्वतंत्र प्रोवर्स होते हैं।<ref name="M. Ben-or, Shafi Goldwasser 1988">M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf Multi prover interactive proofs: How to remove intractability assumptions]. ''Proceedings of the 20th ACM Symposium on Theory of Computing'', pp. 113–121. 1988.</ref> एक बार जब सत्यापनकर्ता ने उन्हें संदेश भेजना शुरू कर दिया तो दोनों नीतियाँ संवाद नहीं कर सकतीं। जैसे यह बताना आसान है कि अपराधी झूठ बोल रहा है या नहीं, यदि उससे और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो एक दुर्भावनापूर्ण सूचक का पता लगाना काफी आसान है जो सत्यापनकर्ता को एक स्ट्रिंग को स्वीकार करने के लिए धोखा देने की कोशिश कर रहा है जो भाषा में नहीं है यदि कोई अन्य सूचक है तो यह हो सकता है के साथ दोबारा जांच करें।
आईपी ​​के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि वेरिफायर को अधिक शक्तिशाली और इतना अव्यवहारिक बनाए बिना इसे और अधिक शक्तिशाली नहीं बनाया जा सकता है। गोल्डवेसर एट अल. अपने 1988 के मल्टी प्रूवर इंटरैक्टिव प्रूफ़्स में इस पर काबू पा लिया: अट्रैक्टिविटी धारणाओं को कैसे दूर करें, जो एमआईपी नामक आईपी के एक प्रकार को परिभाषित करता है जिसमें ''दो'' स्वतंत्र प्रोवर्स होते हैं।<ref name="M. Ben-or, Shafi Goldwasser 1988">M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf Multi prover interactive proofs: How to remove intractability assumptions]. ''Proceedings of the 20th ACM Symposium on Theory of Computing'', pp. 113–121. 1988.</ref> एक बार जब वेरिफायर ने उन्हें मैसेज भेजना शुरू कर दिया तो दोनों नीतियाँ संवाद नहीं कर सकतीं। जैसे यह बताना आसान है कि अपराधी झूठ बोल रहा है या नहीं, यदि उससे और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो एक दुर्भावनापूर्ण प्रूवर का पता लगाना काफी आसान है जो वेरिफायर को एक स्ट्रिंग को एक्सेप्ट करने के लिए धोखा देने की कोशिश कर रहा है जो लैंग्वेज में नहीं है यदि कोई अन्य प्रूवर है तो यह हो सकता है के साथ दोबारा जांच करें।


वास्तव में, यह इतना मददगार है कि बाबई, फ़ोर्टनो, और लुंड यह दिखाने में सक्षम थे कि एमआईपी = [[अगली बार]], सभी समस्याओं का वर्ग जो ''घातीय समय'' में एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] मशीन द्वारा हल किया जा सकता है, एक बहुत बड़ा वर्ग।<ref>László Babai, L. Fortnow, and C. Lund. [http://citeseer.ist.psu.edu/15039.html Non-deterministic exponential time has two-prover interactive protocols]. ''Computational Complexity'', volume 1, pp. 3–40. 1991.</ref> NEXPTIME में PSPACE शामिल है, और माना जाता है कि इसमें पूरी तरह से PSPACE शामिल है। दो से अधिक अतिरिक्त सूक्तियों की निरंतर संख्या जोड़ने से किसी और भाषा की पहचान संभव नहीं हो पाती है। इस परिणाम ने प्रसिद्ध [[पीसीपी प्रमेय]] के लिए मार्ग प्रशस्त किया, जिसे इस प्रमेय का एक छोटा संस्करण माना जा सकता है।
वास्तव में, यह इतना हेल्पफुल है कि बाबई, फ़ोर्टनो, और लुंड यह दिखाने में सक्षम थे कि एमआईपी = [[अगली बार]], सभी समस्याओं का वर्ग जो ''घातीय समय'' में एक [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-डिटर्मिनिस्टिक ट्यूरिंग मशीन]] मशीन द्वारा हल किया जा सकता है, एक बहुत बड़ा वर्ग।<ref>László Babai, L. Fortnow, and C. Lund. [http://citeseer.ist.psu.edu/15039.html Non-deterministic exponential time has two-prover interactive protocols]. ''Computational Complexity'', volume 1, pp. 3–40. 1991.</ref> NEXPTIME में PSPACE शामिल है, और माना जाता है कि इसमें पूरी तरह से PSPACE शामिल है। दो से अधिक अतिरिक्त सूक्तियों की निरंतर संख्या जोड़ने से किसी और लैंग्वेज की पहचान संभव नहीं हो पाती है। इस परिणाम ने प्रसिद्ध [[पीसीपी प्रमेय]] के लिए मार्ग प्रशस्त किया, जिसे इस प्रमेय का एक छोटा संस्करण माना जा सकता है।


एमआईपी में यह सहायक संपत्ति भी है कि एनपी में प्रत्येक भाषा के लिए शून्य-ज्ञान प्रमाण को आईपी द्वारा किए जाने वाले एकतरफा कार्यों की धारणा के बिना वर्णित किया जा सकता है। इसका असर संभवतः अटूट क्रिप्टोग्राफ़िक एल्गोरिदम के डिज़ाइन पर पड़ता है।<ref name="M. Ben-or, Shafi Goldwasser 1988"/>इसके अलावा, एक एमआईपी प्रोटोकॉल केवल निरंतर संख्या में राउंड में आईपी में सभी भाषाओं को पहचान सकता है, और यदि कोई तीसरा प्रोवर जोड़ा जाता है, तो यह NEXPTIME में सभी भाषाओं को निरंतर संख्या में राउंड में पहचान सकता है, जिससे आईपी पर फिर से अपनी शक्ति दिखाई देती है।
एमआईपी में यह सहायक प्रॉपर्टी भी है कि एनपी में प्रत्येक लैंग्वेज के लिए शून्य-ज्ञान प्रूफ को आईपी द्वारा किए जाने वाले एकतरफा कार्यों की धारणा के बिना वर्णित किया जा सकता है। इसका असर संभवतः अटूट क्रिप्टोग्राफ़िक एल्गोरिदम के डिज़ाइन पर पड़ता है।<ref name="M. Ben-or, Shafi Goldwasser 1988"/>इसके अलावा, एक एमआईपी प्रोटोकॉल केवल निरंतर संख्या में राउंड में आईपी में सभी भाषाओं को पहचान सकता है, और यदि कोई तीसरा प्रूवर जोड़ा जाता है, तो यह NEXPTIME में सभी भाषाओं को निरंतर संख्या में राउंड में पहचान सकता है, जिससे आईपी पर फिर से अपनी शक्ति दिखाई देती है।


यह ज्ञात है कि किसी भी स्थिरांक ''k'' के लिए, ''k'' प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी प्रणाली को केवल 2 प्रोवर्स और निरंतर संख्या में राउंड के साथ एक समतुल्य प्रणाली में बदला जा सकता है।<ref>{{cite journal |last1=Ben-Or |first1=Michael |last2=Goldwasser |first2=Shafi |last3=Kilian |first3=Joe |last4=Widgerson |first4=Avi |title=Multi-prover interactive proofs: how to remove intractability |journal=Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing - STOC '88 |date=1988 |pages=113–131 |doi=10.1145/62212.62223 |isbn=0897912640 |s2cid=11008365 |url=http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf |access-date=17 November 2022 |language=en|archive-date=13 July 2010|archive-url=https://web.archive.org/web/20100713035025/http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf}}</ref>
यह ज्ञात है कि किसी भी स्थिरांक ''k'' के लिए, ''k'' प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी सिस्टम को केवल 2 प्रोवर्स और निरंतर संख्या में राउंड के साथ एक समतुल्य सिस्टम में बदला जा सकता है।<ref>{{cite journal |last1=Ben-Or |first1=Michael |last2=Goldwasser |first2=Shafi |last3=Kilian |first3=Joe |last4=Widgerson |first4=Avi |title=Multi-prover interactive proofs: how to remove intractability |journal=Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing - STOC '88 |date=1988 |pages=113–131 |doi=10.1145/62212.62223 |isbn=0897912640 |s2cid=11008365 |url=http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf |access-date=17 November 2022 |language=en|archive-date=13 July 2010|archive-url=https://web.archive.org/web/20100713035025/http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc-bgkw.pdf}}</ref>




=== पीसीपी ===
=== पीसीपी ===
{{main|Probabilistically checkable proof}}
{{main|Probabilistically checkable proof}}
जबकि आईपी के डिजाइनरों ने बाबाई के इंटरैक्टिव प्रूफ सिस्टम के सामान्यीकरण पर विचार किया, वहीं अन्य ने प्रतिबंधों पर विचार किया। एक बहुत ही उपयोगी इंटरैक्टिव प्रूफ सिस्टम पीसीपी(''एफ''(''एन''), ''जी''(''एन'')) है, जो एमए का एक प्रतिबंध है जहां आर्थर केवल ''एफ'' का उपयोग कर सकता है ''(''एन'') यादृच्छिक बिट्स और केवल मर्लिन द्वारा भेजे गए प्रमाण प्रमाण पत्र के ''जी''(''एन'') बिट्स की जांच कर सकते हैं (अनिवार्य रूप से यादृच्छिक पहुंच का उपयोग करके)।
जबकि आईपी के डिजाइनरों ने बाबाई के इंटरैक्टिव प्रूफ सिस्टम के सामान्यीकरण पर विचार किया, वहीं अन्य ने प्रतिबंधों पर विचार किया। एक बहुत ही उपयोगी इंटरैक्टिव प्रूफ सिस्टम पीसीपी(''एफ''(''एन''), ''जी''(''एन'')) है, जो एमए का एक प्रतिबंध है जहां आर्थर केवल ''एफ'' का उपयोग कर सकता है ''(''एन'') यादृच्छिक बिट्स और केवल मर्लिन द्वारा भेजे गए प्रूफ प्रूफ सर्टिफिकेट के ''जी''(''एन'') बिट्स की जांच कर सकते हैं (अनिवार्य रूप से यादृच्छिक पहुंच का उपयोग करके)।


विभिन्न पीसीपी कक्षाओं के बारे में आसानी से साबित होने वाले कई परिणाम हैं। {{tmath|1=\mathsf{PCP}(0,\mathsf{poly})}}, बहुपद-समय मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन प्रमाणपत्र तक पहुंच है, सिर्फ एनपी है। {{tmath|1=\mathsf{PCP}(\mathsf{poly},0)}}, बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली बहुपद-समय मशीनों का वर्ग सह-[[आरपी (जटिलता)]] है। अरोरा और सफरा का पहला बड़ा परिणाम यही था {{sans-serif|1= PCP(log, log) = NP }}; दूसरे शब्दों में कहें तो, यदि एनपी प्रोटोकॉल में सत्यापनकर्ता केवल चुनने के लिए बाध्य है {{tmath|O(\log n)}} प्रमाण प्रमाणपत्र के अंशों को देखने के लिए, इससे तब तक कोई फर्क नहीं पड़ेगा जब तक यह मौजूद है {{tmath|O(\log n)}} उपयोग करने के लिए यादृच्छिक बिट्स।<ref>Sanjeev Arora and [[Shmuel Safra]]. [http://citeseer.ist.psu.edu/arora92probabilistic.html Probabilistic Checking of Proofs: A New Characterization of NP]. ''Journal of the ACM'', volume 45, issue 1, pp. 70–122. January 1998.</ref>
विभिन्न पीसीपी कक्षाओं के बारे में आसानी से साबित होने वाले कई परिणाम हैं। {{tmath|1=\mathsf{PCP}(0,\mathsf{poly})}}, बहुपद-समय मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन सर्टिफिकेट तक पहुंच है, सिर्फ एनपी है। {{tmath|1=\mathsf{PCP}(\mathsf{poly},0)}}, बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली बहुपद-समय मशीनों का वर्ग सह-[[आरपी (जटिलता)|आरपी (कम्प्लेक्सिटी)]] है। अरोरा और सफरा का पहला बड़ा परिणाम यही था {{sans-serif|1= PCP(log, log) = NP }}; दूसरे शब्दों में कहें तो, यदि एनपी प्रोटोकॉल में वेरिफायर केवल चुनने के लिए बाध्य है {{tmath|O(\log n)}} प्रूफ सर्टिफिकेट के अंशों को देखने के लिए, इससे तब तक कोई फर्क नहीं पड़ेगा जब तक यह उपस्थित है {{tmath|O(\log n)}} उपयोग करने के लिए यादृच्छिक बिट्स।<ref>Sanjeev Arora and [[Shmuel Safra]]. [http://citeseer.ist.psu.edu/arora92probabilistic.html Probabilistic Checking of Proofs: A New Characterization of NP]. ''Journal of the ACM'', volume 45, issue 1, pp. 70–122. January 1998.</ref>
इसके अलावा, पीसीपी प्रमेय का दावा है कि प्रमाण पहुंच की संख्या को सभी तरह से एक स्थिरांक तक लाया जा सकता है। वह है, {{tmath|1=\mathsf{NP} = \mathsf{PCP}(\mathsf{log}, O(1))}}.<ref>Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. [http://citeseer.ist.psu.edu/376426.html Proof Verification and the Hardness of Approximation Problems]. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.</ref> उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम मौजूद नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब [[सन्निकटन की कठोरता]] नामक क्षेत्र में किया जाता है।
इसके अलावा, पीसीपी प्रमेय का दावा है कि प्रूफ पहुंच की संख्या को सभी तरह से एक स्थिरांक तक लाया जा सकता है। वह है, {{tmath|1=\mathsf{NP} = \mathsf{PCP}(\mathsf{log}, O(1))}}.<ref>Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. [http://citeseer.ist.psu.edu/376426.html Proof Verification and the Hardness of Approximation Problems]. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.</ref> उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम उपस्थित नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब [[सन्निकटन की कठोरता]] नामक क्षेत्र में किया जाता है।


== यह भी देखें ==
== यह भी देखें ==
* [[ओरेकल मशीन]]
* [[ओरेकल मशीन]]
* [[ज्ञान का प्रमाण]]
* [[ज्ञान का प्रमाण|ज्ञान का प्रूफ]]


== संदर्भ ==
== संदर्भ ==

Revision as of 15:33, 24 July 2023

Not to be confused with प्रमाण सहायक.
एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।

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

सभी इंटरैक्टिव प्रूफ सिस्टम की दो आवश्यकताएँ होती हैं:

  • कम्प्लीटनेस: यदि कथन सत्य है, तो ऑनेस्ट वेरिफायर (अर्थात प्रोटोकॉल का ठीक से पालन करने वाला) ऑनेस्ट वेरिफायर को कन्विंस कर सकता है कि यह वास्तव में सत्य है।
  • साउंडनेस: यदि कथन गलत है, तो कोई भी प्रूवर, भले ही वह प्रोटोकॉल का पालन न करता हो, ऑनेस्ट वेरिफायर को यह कन्विंस नहीं कर सकता कि यह सत्य है, कुछ छोटी प्रोबेबिलिटी को छोड़कर।

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

पृष्ठभूमि

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

कुछ के लिए ।

जब तक साउंडनेस एरर वेरिफायर के संभावित रनिंग टाइम के बहुपद अंश से बंधी होती है (यानी) ), साउंडनेस को बढ़ाना हमेशा संभव होता है जब तक कि वेरिफायर के रनिंग टाइम के सापेक्ष साउंडनेस एरर नेग्लिजिबल फंक्शन न हो जाए। यह प्रूफ को दोहराने और सभी प्रूफ वेरीफाई होने पर ही एक्सेप्ट करने से प्राप्त होता है। बाद दोहराव, एक ध्वनि एरर तक कम कर दिया जाएगा। [1]


इंटरैक्टिव प्रमाणों की श्रेणियां

एनपी

कम्प्लेक्सिटी क्लास [[एनपी (कम्प्लेक्सिटी)]] को एक बहुत ही सिंपल प्रूफ सिस्टम के रूप में देखा जा सकता है। इस सिस्टम में, वेरिफायर एक डिटर्मिनिस्टिक, पोलीनोमिअल-साइज (एक पी (कम्प्लेक्सिटी) मशीन) है। प्रोटोकॉल है:

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

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

आर्थर-मर्लिन और मर्लिन-आर्थर प्रोटोकॉल

Main article: मर्लिन-आर्थर प्रोटोकॉल

यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 1985 तक नहीं था कि रिसर्चर के दो इंडिपेंडेंट ग्रुप द्वारा इंटरैक्शन के माध्यम से गणना की अवधारणा की कल्पना की गई थी (कम्प्लेक्सिटी थ्योरी के संदर्भ में)। एक दृष्टिकोण, लास्ज़लो बाबाई द्वारा, जिन्होंने "ट्रेडिंग ग्रुप थ्योरी फॉर रैंडमनेस" प्रकाशित किया, [2] आर्थर-मर्लिन ('एएम') क्लास हायरार्की को परिभाषित किया। इस प्रस्तुति में, आर्थर (वेरिफायर) एक प्रोबबिलिस्टिक ट्यूरिंग मशीन, पोलीनोमिअल-टाइम मशीन है, जबकि मर्लिन (वेरीफायर) के पास अनबाउंडेड रिसोर्स हैं।

विशेष रूप से क्लास 'एमए' उपरोक्त एनपी इंटरैक्शन का एक सिंपल जनरलाइज़ेशन है जिसमें वेरिफायर डिटर्मिनिस्टिक के स्थान पर डेटर्मीनिस्टिक है। साथ ही, यह अपेक्षा करने के स्थान पर कि वेरिफायर हमेशा वैलिड सर्टिफिकेट एक्सेप्ट करें और इनवैलिड सर्टिफिकेट रिजेक्ट करें, यह अधिक लेनिएंट है:

  • 'कम्प्लीटनेस:' यदि स्ट्रिंग लैंग्वेज में है, तो प्रूवर को एक प्रूफ सर्टिफिकेट देने में सक्षम होना चाहिए, जिसे वेरिफायर कम से कम 2/3 प्रोबेबिलिटी के साथ एक्सेप्ट करेगा (वेरिफायर के रैंडम चॉइस के आधार पर)।
  • 'साउंडनेस:' यदि स्ट्रिंग लैंग्वेज में नहीं है, तो कोई भी प्रूवर, चाहे वह कितनी भी मालिशियस क्यों न हो, वेरिफायर को 1/3 से अधिक प्रोबेबिलिटी वाली स्ट्रिंग को एक्सेप्ट करने के लिए मनाने में सक्षम नहीं होगी।

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

पब्लिक कॉइन प्रोटोकॉल बनाम प्राइवेट कॉइन प्रोटोकॉल

पब्लिक कॉइन प्रोटोकॉल में, वेरिफायर द्वारा चुने गए रैंडम चॉइस को पब्लिक किया जाता है। वे प्राइवेट कॉइन प्रोटोकॉल में प्राइवेट रहते हैं।

उसी सम्मेलन में जहां बाबई ने 'एमए' के ​​लिए अपनी प्रूफ सिस्टम को परिभाषित किया, शफ़ी गोल्डवेसर, सिल्वियो मिकाली और चार्ल्स रैकॉफ़ [3] इंटरैक्टिव प्रूफ सिस्टम आईपी [एफ(एन)] को परिभाषित करने वाला एक पेपर पब्लिश किया। इसमें एमए प्रोटोकॉल के समान मशीनें हैं, सिवाय इसके कि एन आकार के इनपुट के लिए एफ(एन) राउंड की अनुमति है। प्रत्येक दौर में, वेरिफायर गणना करता है और प्रूवर को एक मैसेज भेजता है, और प्रूवर गणना करता है और वेरिफायर को जानकारी वापस भेजता है। अंत में वेरिफायर को अपना निर्णय लेना होगा। उदाहरण के लिए, एक आईपी[3] प्रोटोकॉल में, अनुक्रम वीपीवीपीवीपीवी होगा, जहां वी एक वेरिफायर टर्न है और पी एक प्रूवर टर्न है।

आर्थर-मर्लिन प्रोटोकॉल में, बाबई ने एक समान वर्ग AM[f(n)] को परिभाषित किया, जो f(n) राउंड की अनुमति देता था, लेकिन उन्होंने एक अतिरिक्त कंडीशन रखी कि मशीन: वेरिफायर को अपनी गणना में उपयोग किए जाने वाले सभी रैंडम बिट्स को प्रूवर को दिखाना होगा। इसका परिणाम यह होता है कि वेरिफायर प्रूवर से कुछ भी नहीं छिपा सकता है, क्योंकि प्रूवर इतना शक्तिशाली है कि वेरिफायर जो कुछ भी करता है उसका अनुकरण कर सकता है यदि उसे पता हो कि उसने कौन से यादृच्छिक बिट्स का उपयोग किया है। इसे पब्लिक कॉइन प्रोटोकॉल कहा जाता है, क्योंकि यादृच्छिक बिट्स (कॉइन फ्लिप) दोनों मशीनों पर दिखाई देते हैं। इसके विपरीत आईपी दृष्टिकोण को प्राइवेट कॉइन प्रोटोकॉल कहा जाता है।

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

1986 में, गोल्डवेसर और माइकल सिप्सर [4] दिखाया गया है, शायद आश्चर्यजनक रूप से, कि प्रूवर से कॉइन के फ्लिप को छिपाने की वेरिफायर की क्षमता आखिरकार कुछ भी अच्छा नहीं करती है, जिसमें केवल दो और राउंड के साथ एक आर्थर-मर्लिन पब्लिक कॉइन प्रोटोकॉल सभी समान भाषाओं को पहचान सकता है। नतीजा यह है कि पब्लिक-कॉइन और प्राइवेट-कॉइन प्रोटोकॉल लगभग बराबर हैं। वास्तव में, जैसा कि बाबई ने 1988 में दिखाया था, सभी स्थिरांक k के लिए AM[k]=AM, इसलिए IP[k] का AM पर कोई लाभ नहीं है। [5]

इन क्लासेज की पावर को प्रदर्शित करने के लिए, ग्राफ इसोमोर्फिसम प्रॉब्लम पर विचार करें, यह निर्धारित करने की प्रॉब्लम कि क्या एक ग्राफ के वर्टाइसेस को परम्यूट करना संभव है ताकि यह दूसरे ग्राफ के समान हो। यह प्रॉब्लम एनपी में है, क्योंकि प्रूफ सर्टिफिकेट परम्यूटेशन है जो ग्राफ़ को समान बनाता है। यह पता चला है कि ग्राफ इसोमोर्फिसम प्रॉब्लम का पूरक (कम्प्लेक्सिटी), एक सह-एनपी प्रॉब्लम जिसे एनपी में नहीं जाना जाता है, में एक एएम एल्गोरिदम है और इसे देखने का सबसे अच्छा तरीका एक प्राइवेट कॉइन एल्गोरिदम के माध्यम से है। [6]


आईपी

Main article: आईपी (कम्प्लेक्सिटी)

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


क्यूआईपी

Main article: QIP (complexity)

यदि हम सिस्टम के तत्वों को क्वांटम गणना का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित कम्प्लेक्सिटी वर्ग को क्यूआईपी कहा जाता है।[8] परिणामों की एक श्रृंखला 2010 में QIP = PSPACE की सफलता में परिणत हुई।[9][10]


शून्य ज्ञान

Main article: Zero-knowledge proof

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


एमआईपी

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

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

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

यह ज्ञात है कि किसी भी स्थिरांक k के लिए, k प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी सिस्टम को केवल 2 प्रोवर्स और निरंतर संख्या में राउंड के साथ एक समतुल्य सिस्टम में बदला जा सकता है।[14]


पीसीपी

Main article: Probabilistically checkable proof

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

विभिन्न पीसीपी कक्षाओं के बारे में आसानी से साबित होने वाले कई परिणाम हैं। , बहुपद-समय मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन सर्टिफिकेट तक पहुंच है, सिर्फ एनपी है। , बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली बहुपद-समय मशीनों का वर्ग सह-आरपी (कम्प्लेक्सिटी) है। अरोरा और सफरा का पहला बड़ा परिणाम यही था PCP(log, log) = NP; दूसरे शब्दों में कहें तो, यदि एनपी प्रोटोकॉल में वेरिफायर केवल चुनने के लिए बाध्य है प्रूफ सर्टिफिकेट के अंशों को देखने के लिए, इससे तब तक कोई फर्क नहीं पड़ेगा जब तक यह उपस्थित है उपयोग करने के लिए यादृच्छिक बिट्स।[15] इसके अलावा, पीसीपी प्रमेय का दावा है कि प्रूफ पहुंच की संख्या को सभी तरह से एक स्थिरांक तक लाया जा सकता है। वह है, .[16] उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम उपस्थित नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब सन्निकटन की कठोरता नामक क्षेत्र में किया जाता है।

यह भी देखें

संदर्भ

  1. ↑ Goldreich, Oded (2002), Zero-Knowledge twenty years after its invention, ECCC TR02-063.
  2. ↑ László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.
  3. ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989). "इंटरैक्टिव प्रूफ सिस्टम की ज्ञान जटिलता" (PDF). SIAM Journal on Computing. 18 (1): 186–208. doi:10.1137/0218012. ISSN 1095-7111. Extended abstract
  4. ↑ Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of ACM STOC'86, pp. 58–68. 1986.
  5. ↑ László Babai and Shlomo Moran. Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36: p.254–276. 1988.
  6. ↑ 6.0 6.1 O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690–728. July 1991.
  7. ↑ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
  8. ↑ Tsuyoshi Ito; Hirotada Kobayashi; John Watrous (2010). "कमजोर त्रुटि सीमाओं के साथ क्वांटम इंटरैक्टिव प्रमाण". arXiv:1012.4427v2 [quant-ph].
  9. ↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010). "QIP = PSPACE". STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing. ACM. pp. 573–582. ISBN 978-1-4503-0050-6.
  10. ↑ Aaronson, S. (2010). "QIP = PSPACE breakthrough". Communications of the ACM. 53 (12): 101. doi:10.1145/1859204.1859230. S2CID 34380788.
  11. ↑ Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [1]
  12. ↑ 12.0 12.1 M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions. Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 113–121. 1988.
  13. ↑ László Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, volume 1, pp. 3–40. 1991.
  14. ↑ Ben-Or, Michael; Goldwasser, Shafi; Kilian, Joe; Widgerson, Avi (1988). "Multi-prover interactive proofs: how to remove intractability" (PDF). Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing - STOC '88 (in English): 113–131. doi:10.1145/62212.62223. ISBN 0897912640. S2CID 11008365. Archived from the original (PDF) on 13 July 2010. Retrieved 17 November 2022.
  15. ↑ Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM, volume 45, issue 1, pp. 70–122. January 1998.
  16. ↑ Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and the Hardness of Approximation Problems. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 13–22. 1992.


पाठ्यपुस्तकें


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=इंटरैक्टिव_प्रमाण_प्रणाली&oldid=232338’