View source for इंटरैक्टिव प्रमाण प्रणाली

{{distinguish|प्रमाण सहायक}}
[[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>\Pr[(\perp,(\text{accept}))\gets (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)] < \epsilon.</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>



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

=== एनपी ===

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

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

=== आर्थर-मर्लिन और मर्लिन-आर्थर प्रोटोकॉल ===
{{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> आर्थर-मर्लिन ('एएम') क्लास हायरार्की को परिभाषित किया। इस प्रस्तुति में, आर्थर (वेरिफायर) एक [[संभाव्य ट्यूरिंग मशीन|प्रोबबिलिस्टिक ट्यूरिंग मशीन]], पोलीनोमिअल-टाइम मशीन है, जबकि मर्लिन (वेरीफायर) के पास अनबाउंडेड रिसोर्स हैं।

विशेष रूप से क्लास 'एमए' उपरोक्त एनपी इंटरैक्शन का एक सिंपल जनरलाइज़ेशन है जिसमें वेरिफायर डिटर्मिनिस्टिक के स्थान पर डेटर्मीनिस्टिक है। साथ ही, यह अपेक्षा करने के स्थान पर कि वेरिफायर हमेशा वैलिड सर्टिफिकेट एक्सेप्ट करें और इनवैलिड सर्टिफिकेट रिजेक्ट करें, यह अधिक लेनिएंट है:
* 'कम्प्लीटनेस:' यदि स्ट्रिंग लैंग्वेज में है, तो प्रूवर को एक प्रूफ सर्टिफिकेट देने में सक्षम होना चाहिए, जिसे वेरिफायर कम से कम 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] प्रोटोकॉल में, अनुक्रम वीपीवीपीवीपीवी होगा, जहां वी एक वेरिफायर टर्न है और पी एक प्रूवर टर्न है।

आर्थर-मर्लिन प्रोटोकॉल में, बाबई ने एक समान वर्ग 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>



=== आईपी ===
{{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>


=== क्यूआईपी ===
{{main|क्यूआईपी (कम्प्लेक्सिटी)}}

यदि हम सिस्टम के एलिमेंट को [[क्वांटम गणना|क्वांटम कम्प्यूटेशन]] का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित कम्प्लेक्सिटी क्लास को क्यूआईपी कहा जाता है। <ref>{{cite arXiv|eprint=1012.4427v2|author1=Tsuyoshi Ito|author2=Hirotada Kobayashi|author3=John Watrous|title=कमजोर त्रुटि सीमाओं के साथ क्वांटम इंटरैक्टिव प्रमाण|class=quant-ph|year=2010}}</ref> रिजल्ट की एक श्रृंखला 2010 में क्यूआईपी = पीस्पेस की सफलता में कलमिनेट हुई। <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|जीरो-नॉलेज प्रूफ}}

न केवल इंटरैक्टिव प्रूफ सिस्टम उन प्रॉब्लम को हल कर सकते हैं जिन पर एनपी में विश्वास नहीं किया जाता है, बल्कि वन-वे फंक्शन के अस्तित्व के बारे में धारणाओं के अंतर्गत, एक प्रूवर वेरिफायर को समाधान के बारे में जानकारी दिए बिना समाधान के बारे में कन्विंस कर सकता है। यह तब महत्वपूर्ण है जब वेरिफायर पर पूर्ण समाधान पर ट्रस्ट नहीं किया जा सकता है। पहले तो यह असंभव लगता है कि वेरिफायर कन्विंस हो सके कि कोई सोल्युशन है जब वेरिफायर ने सर्टिफिकेट नहीं देखा है, लेकिन ऐसे प्रूफ, जिन्हें [[शून्य-ज्ञान प्रमाण|जीरो-नॉलेज प्रूफ]] के रूप में जाना जाता है, वास्तव में एनपी में सभी प्रॉब्लम के लिए उपस्थित माने जाते हैं और [[क्रिप्टोग्राफी]] में मूल्यवान हैं। स्पेसिफिक नंबर थेओरेटिक लैंग्वेजेज के लिए गोल्डवेसर, मिकाली और रैकॉफ द्वारा आईपी पर मूल 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> एक बार जब वेरिफायर ने उन्हें मैसेज भेजना प्रारम्भ कर दिया तो दोनों प्रूवर कम्यूनिकेट नहीं कर सकते। जैसे यह बताना आसान है कि अपराधी झूठ बोल रहा है या नहीं, यदि उससे और उसके साथी से अलग-अलग कमरों में इंटेररोगेशन की जाती है, तो एक मालिसियस प्रूवर का पता लगाना काफी आसान है जो वेरिफायर को एक स्ट्रिंग को एक्सेप्ट करने के लिए ट्रिक करने का प्रयास कर रहा है जो लैंग्वेज में नहीं है यदि कोई अन्य प्रूवर है तो यह हो सकता है कि उसके साथ डबल-चेक करें।

वास्तव में, यह इतना हेल्पफुल है कि बाबई, फ़ोर्टनो, और लुंड यह दिखाने में सक्षम थे कि एमआईपी = [[अगली बार|एनईएक्सपीटाइम]], सभी प्रॉब्लम का वर्ग जो एक्सपोनेंशियल टाइम में एक [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-डिटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। <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> एनईएक्सपीटाइम में पीस्पेस सम्मिलित है, और माना जाता है कि इसमें पूरी तरह से पीस्पेस सम्मिलित है। दो से अधिक एडिशनल प्रूवर की निरंतर संख्या जोड़ने से किसी और लैंग्वेज की पहचान संभव नहीं हो पाती है। इस परिणाम ने प्रसिद्ध [[पीसीपी प्रमेय]] के लिए मार्ग प्रशस्त किया, जिसे इस प्रमेय का एक छोटा संस्करण माना जा सकता है।

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

यह ज्ञात है कि किसी भी स्थिरांक ''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|प्रोबबिलिस्टिकली चेकेबल प्रूफ}}
जबकि आईपी के डिजाइनरों ने बाबाई के इंटरैक्टिव प्रूफ सिस्टम के सामान्यीकरण पर विचार किया, वहीं अन्य ने प्रतिबंधों पर विचार किया। एक बहुत ही उपयोगी इंटरैक्टिव प्रूफ सिस्टम पीसीपी(''एफ''(''एन''), ''जी''(''एन'')) है, जो एमए का एक रेस्ट्रिक्शन है जहां आर्थर केवल एफ (एन) का उपयोग कर सकता है यादृच्छिक बिट्स और केवल मर्लिन द्वारा भेजे गए प्रूफ सर्टिफिकेट के जी(एन) बिट्स की जांच कर सकते हैं (अनिवार्य रूप से रैंडम एक्सेस का उपयोग करके)।

विभिन्न पीसीपी कक्षाओं के बारे में आसानी से सिद्ध होने वाले कई परिणाम हैं। {{tmath|1=\mathsf{PCP}(0,\mathsf{poly})}}, पोलीनोमिअल-टाइम मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन सर्टिफिकेट तक पहुंच है, सिर्फ एनपी है। {{tmath|1=\mathsf{PCP}(\mathsf{poly},0)}}, बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली पोलीनोमिअल-टाइम मशीनों का वर्ग co-[[आरपी (जटिलता)|RP (कम्प्लेक्सिटी)]] है। अरोरा और सफरा का पहला बड़ा परिणाम {{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> उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह सिद्ध करने के लिए किया कि कुछ एनपी-पूर्ण प्रॉब्लम के अनुकूलन संस्करणों के लिए अप्प्रोक्सिमेशन एल्गोरिदम उपस्थित नहीं हैं जब तक कि पी = एनपी न हो। ऐसी प्रॉब्लम का अध्ययन अब [[हार्डनेस ऑफ़ अप्प्रोक्सिमेशन]] नामक क्षेत्र में किया जाता है।

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

== संदर्भ ==
{{Reflist}}


== पाठ्यपुस्तकें ==
* Arora, Sanjeev; Barak, Boaz, [http://www.cs.princeton.edu/theory/complexity/ "Complexity Theory: A Modern Approach"], Cambridge University Press, March 2009.
* {{cite book | author = Michael Sipser | author-link = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 978-0-534-94728-6 | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 10.4: Interactive Proof Systems, pp.&nbsp;354&ndash;366.
* {{cite book|author = Christos Papadimitriou|author-link = Christos Papadimitriou| year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 978-0-201-53082-7}} Section 19.2: Games against nature and interactive protocols, pp.&nbsp;469&ndash;480.


== बाहरी संबंध ==
* Dexter Kozen. [http://www.cs.cornell.edu/Courses/cs682/2004sp/Lectures/l15-ip.pdf Interactive Proofs]. CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
* [[Complexity Zoo]]: <!-- to do: use [[template:CZoo]] -->
** [https://web.archive.org/web/20100727022118/http://qwiki.stanford.edu/wiki/Complexity_Zoo:M#ma MA], [https://web.archive.org/web/20100727022118/http://qwiki.stanford.edu/wiki/Complexity_Zoo:M#maprime MA'], [https://web.archive.org/web/20100727022118/http://qwiki.stanford.edu/wiki/Complexity_Zoo:M#maexp MAEXP], [https://web.archive.org/web/20100727022118/http://qwiki.stanford.edu/wiki/Complexity_Zoo:M#mae MAE]
** [https://web.archive.org/web/20100727013744/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AA#am AM], [https://web.archive.org/web/20100727013744/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AA#amexp AMEXP], [https://web.archive.org/web/20100727013744/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AA#amicoam AM intersect co-AM], [https://web.archive.org/web/20100727013744/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AA#ampolylog AM<nowiki>[polylog]</nowiki>], [http://qwiki.caltech.edu/wiki/Complexity_Zoo:C#coam coAM], [https://web.archive.org/web/20100727033302/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AB#bpnp BP•NP]
** [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qma QMA], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qma+ QMA+], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qma2 QMA(2)], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qmalog QMA<sub>log</sub>], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qmam QMAM]
** [https://web.archive.org/web/20100727062035/http://qwiki.stanford.edu/wiki/Complexity_Zoo:I#ip IP], [https://web.archive.org/web/20100727022118/http://qwiki.stanford.edu/wiki/Complexity_Zoo:M#mip MIP], [https://web.archive.org/web/20100727062035/http://qwiki.stanford.edu/wiki/Complexity_Zoo:I#ipp IPP], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qip QIP], [https://web.archive.org/web/20100727032326/http://qwiki.stanford.edu/wiki/Complexity_Zoo:Q#qip2 QIP(2)], [https://web.archive.org/web/20081023050027/http://qwiki.stanford.edu/wiki/Complexity_Zoo:C#compip compIP], [https://web.archive.org/web/20100727052636/http://qwiki.stanford.edu/wiki/Complexity_Zoo:F#frip frIP]
** [https://web.archive.org/web/20081204124245/http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pcp PCP(r(n),q(n))]
* Larry Gonick. "[https://web.archive.org/web/20120722015436/http://theory.cs.uchicago.edu/merlin/ Proof Positive?]". A comic strip about interactive proof systems.

{{ComplexityClasses}}

{{DEFAULTSORT:Interactive Proof System}}

[[Category:Articles with hatnote templates targeting a nonexistent page|Interactive Proof System]]
[[Category:CS1 English-language sources (en)]]
[[Category:Collapse templates|Interactive Proof System]]
[[Category:Created On 08/07/2023|Interactive Proof System]]
[[Category:Machine Translated Page|Interactive Proof System]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Interactive Proof System]]
[[Category:Pages with script errors|Interactive Proof System]]
[[Category:Sidebars with styles needing conversion|Interactive Proof System]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Interactive Proof System]]
[[Category:Templates generating microformats|Interactive Proof System]]
[[Category:Templates that are not mobile friendly|Interactive Proof System]]
[[Category:Templates using TemplateData|Interactive Proof System]]
[[Category:Wikipedia metatemplates|Interactive Proof System]]
[[Category:कम्प्यूटेशनल जटिलता सिद्धांत|Interactive Proof System]]