इंटरैक्टिव प्रमाण प्रणाली: Difference between revisions
(Created page with "{{distinguish|Proof assistant}} File:Interactive proof (complexity).svg|thumb|300px|एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल क...") |
No edit summary |
||
Line 1: | Line 1: | ||
{{distinguish| | {{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>\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\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| | {{main|मर्लिन-आर्थर प्रोटोकॉल}} | ||
यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 1985 तक नहीं था कि | |||
यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 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| | {{main|आईपी (कम्प्लेक्सिटी)}} | ||
1992 में, [[आदि शमीर]] ने | '''प्राइवेट कॉइन हेल्पफुल न'''हीं हो सकते हैं, लेकिन इंटरेक्शन के अधिक दौर हेल्पफुल होते हैं। यदि हम संभाव्य वेरिफायर मशीन और सर्व-शक्तिशाली प्रूवर को बहुपद संख्या में राउंड के लिए इंटरेक्शन करने की अनुमति देते हैं, तो हमें समस्याओं का वर्ग मिलता है जिसे आईपी कहा जाता है। | ||
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> | ||
=== शून्य ज्ञान === | === शून्य ज्ञान === | ||
{{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> | ||
=== एमआईपी === | === एमआईपी === | ||
आईपी के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि | आईपी के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि वेरिफायर को अधिक शक्तिशाली और इतना अव्यवहारिक बनाए बिना इसे और अधिक शक्तिशाली नहीं बनाया जा सकता है। गोल्डवेसर एट अल. अपने 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 name="M. Ben-or, Shafi Goldwasser 1988"/>इसके अलावा, एक एमआईपी प्रोटोकॉल केवल निरंतर संख्या में राउंड में आईपी में सभी भाषाओं को पहचान सकता है, और यदि कोई तीसरा प्रूवर जोड़ा जाता है, तो यह NEXPTIME में सभी भाषाओं को निरंतर संख्या में राउंड में पहचान सकता है, जिससे आईपी पर फिर से अपनी शक्ति दिखाई देती है। | ||
यह ज्ञात है कि किसी भी स्थिरांक ''k'' के लिए, ''k'' प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी | यह ज्ञात है कि किसी भी स्थिरांक ''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}(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> उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम उपस्थित नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब [[सन्निकटन की कठोरता]] नामक क्षेत्र में किया जाता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ओरेकल मशीन]] | * [[ओरेकल मशीन]] | ||
* [[ज्ञान का प्रमाण]] | * [[ज्ञान का प्रमाण|ज्ञान का प्रूफ]] | ||
== संदर्भ == | == संदर्भ == |
Revision as of 15:33, 24 July 2023
कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी में, इंटरैक्टिव प्रूफ सिस्टम एक एब्स्ट्रैक्ट मशीन है जो दो पक्षों के बीच मैसेज के आदान-प्रदान के रूप में गणना करती है: एक प्रूवर और एक वेरिफायर। पार्टियां यह सुनिश्चित करने के लिए मैसेज का आदान-प्रदान करके इंटरैक्ट करती हैं कि दी गई स्ट्रिंग (कंप्यूटर विज्ञान) फॉर्मल लैंग्वेज से संबंधित है या नहीं। वेरिफायर के पास असीमित कम्प्यूटेशनल रिसोर्स होते हैं लेकिन उस पर विश्वास नहीं किया जा सकता है, जबकि वेरिफायर के पास बॉउंडेड कम्प्यूटेशन पावर होती है लेकिन यह माना जाता है कि वह हमेशा ऑनेस्ट रहता है। वेरिफायर और वेरिफायर के बीच मैसेज तब तक भेजे जाते हैं जब तक कि वेरिफायर के पास प्रॉब्लम का उत्तर न हो और वह आश्वस्त न हो जाए कि यह सही है।
सभी इंटरैक्टिव प्रूफ सिस्टम की दो आवश्यकताएँ होती हैं:
- कम्प्लीटनेस: यदि कथन सत्य है, तो ऑनेस्ट वेरिफायर (अर्थात प्रोटोकॉल का ठीक से पालन करने वाला) ऑनेस्ट वेरिफायर को कन्विंस कर सकता है कि यह वास्तव में सत्य है।
- साउंडनेस: यदि कथन गलत है, तो कोई भी प्रूवर, भले ही वह प्रोटोकॉल का पालन न करता हो, ऑनेस्ट वेरिफायर को यह कन्विंस नहीं कर सकता कि यह सत्य है, कुछ छोटी प्रोबेबिलिटी को छोड़कर।
सिस्टम का स्पेसिफिक नेचर, और इसलिए भाषाओं की कम्प्लेक्सिटी क्लास जिसे वह पहचान सकता है, इस बात पर निर्भर करता है कि वेरिफायर पर किस प्रकार की सीमाएँ लगाई गई हैं, साथ ही उसे कौन सी क्षमताएँ दी गई हैं - उदाहरण के लिए, अधिकांश इंटरैक्टिव प्रूफ सिस्टम गंभीर रूप से वेरिफायर की यादृच्छिक विकल्प बनाने की क्षमता निर्भर करते हैं। यह आदान-प्रदान किए गए मैसेज की प्रकृति पर भी निर्भर करता है - उनमें कितने और क्या हो सकते हैं। केवल एक मशीन का उपयोग करके परिभाषित ट्रेडिशनल कम्प्लेक्सिटी क्लासेज के लिए इंटरएक्टिव प्रूफ सिस्टम में कुछ महत्वपूर्ण इम्प्लीकेशन पाए गए हैं। इंटरैक्टिव प्रूफ सिस्टम का वर्णन करने वाली मुख्य कम्प्लेक्सिटी क्लासेज एएम (कम्प्लेक्सिटी) और आईपी (कम्प्लेक्सिटी) हैं।
पृष्ठभूमि
प्रत्येक इंटरैक्टिव प्रूफ सिस्टम स्ट्रिंग्स की एक फॉर्मल लैंग्वेज को परिभाषित करता है। प्रूफ सिस्टम की साउंडनेस उस प्रॉपर्टी को संदर्भित करती है जिसे कोई भी नीति वेरिफायर रॉंग स्टेटमेंट के लिए कुछ छोटी संभावनाओं को छोड़कर एक्सेप्ट नहीं कर सकता है। इस प्रोबेबिलिटी की ऊपरी सीमा को प्रूफ सिस्टम की साउंडनेस एरर के रूप में जाना जाता है। अधिक औपचारिक रूप से, प्रत्येक प्रोवेर और हर के लिए :
कुछ के लिए ।
जब तक साउंडनेस एरर वेरिफायर के संभावित रनिंग टाइम के बहुपद अंश से बंधी होती है (यानी) ), साउंडनेस को बढ़ाना हमेशा संभव होता है जब तक कि वेरिफायर के रनिंग टाइम के सापेक्ष साउंडनेस एरर नेग्लिजिबल फंक्शन न हो जाए। यह प्रूफ को दोहराने और सभी प्रूफ वेरीफाई होने पर ही एक्सेप्ट करने से प्राप्त होता है। बाद दोहराव, एक ध्वनि एरर तक कम कर दिया जाएगा। [1]
इंटरैक्टिव प्रमाणों की श्रेणियां
एनपी
कम्प्लेक्सिटी क्लास [[एनपी (कम्प्लेक्सिटी)]] को एक बहुत ही सिंपल प्रूफ सिस्टम के रूप में देखा जा सकता है। इस सिस्टम में, वेरिफायर एक डिटर्मिनिस्टिक, पोलीनोमिअल-साइज (एक पी (कम्प्लेक्सिटी) मशीन) है। प्रोटोकॉल है:
- प्रूवर इनपुट को देखता है और अपनी अनलिमिटेड पावर का उपयोग करके समाधान की गणना करता है और एक पोलीनोमिअल-साइज प्रूफ सर्टिफिकेट लौटाता है।
- वेरिफायर वेरीफाई करता है कि सर्टिफिकेट डिटर्मिनिस्टिक बहुपद समय में वैलिड है। यदि यह वैलिड है, तो यह एक्सेप्ट करता है; अन्यथा, यह रिजेक्ट कर देता है।
ऐसी स्तिथि में जहां एक वैलिड प्रूफ सर्टिफिकेट उपस्थित है, प्रूवर हमेशा उस सर्टिफिकेट को देकर वेरिफायर को एक्सेप्ट करने में सक्षम होता है। ऐसी स्तिथि में जहां कोई वैलिड प्रूफ सर्टिफिकेट नहीं है, हालांकि, इनपुट लैंग्वेज में नहीं है, और कोई भी प्रूवर, चाहे वह कितना भी मालिसियस हो, वेरिफायर को अन्यथा मना नहीं सकता है, क्योंकि किसी भी प्रूफ सर्टिफिकेट को रिजेक्ट कर दिया जाएगा।
आर्थर-मर्लिन और मर्लिन-आर्थर प्रोटोकॉल
यद्यपि एनपी को इंटरैक्शन का उपयोग करने के रूप में देखा जा सकता है, यह 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]
आईपी
प्राइवेट कॉइन हेल्पफुल नहीं हो सकते हैं, लेकिन इंटरेक्शन के अधिक दौर हेल्पफुल होते हैं। यदि हम संभाव्य वेरिफायर मशीन और सर्व-शक्तिशाली प्रूवर को बहुपद संख्या में राउंड के लिए इंटरेक्शन करने की अनुमति देते हैं, तो हमें समस्याओं का वर्ग मिलता है जिसे आईपी कहा जाता है। 1992 में, आदि शमीर ने कम्प्लेक्सिटी थ्योरी के केंद्रीय परिणामों में से एक में खुलासा किया कि आईपी PSPACE के बराबर है, बहुपद अंतरिक्ष में एक साधारण डिटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल की जाने वाली समस्याओं का वर्ग।[7]
क्यूआईपी
यदि हम सिस्टम के तत्वों को क्वांटम गणना का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित कम्प्लेक्सिटी वर्ग को क्यूआईपी कहा जाता है।[8] परिणामों की एक श्रृंखला 2010 में QIP = PSPACE की सफलता में परिणत हुई।[9][10]
शून्य ज्ञान
न केवल इंटरैक्टिव प्रूफ सिस्टम उन समस्याओं को हल कर सकते हैं जिन पर एनपी में विश्वास नहीं किया जाता है, बल्कि एक-तरफ़ा कार्यों के अस्तित्व के बारे में धारणाओं के तहत, एक प्रूवर वेरिफायर को समाधान के बारे में जानकारी दिए बिना समाधान के बारे में आश्वस्त कर सकता है। यह तब महत्वपूर्ण है जब वेरिफायर पर पूर्ण समाधान पर भरोसा नहीं किया जा सकता है। पहले तो यह असंभव लगता है कि वेरिफायर आश्वस्त हो सके कि कोई समाधान है जब वेरिफायर ने सर्टिफिकेट नहीं देखा है, लेकिन ऐसे प्रूफ, जिन्हें शून्य-ज्ञान प्रूफ के रूप में जाना जाता है, वास्तव में एनपी में सभी समस्याओं के लिए उपस्थित माने जाते हैं और मूल्यवान हैं क्रिप्टोग्राफी. विशिष्ट संख्या सैद्धांतिक भाषाओं के लिए गोल्डवेसर, मिकाली और रैकॉफ द्वारा आईपी पर मूल 1985 पेपर में शून्य-ज्ञान प्रमाणों का पहली बार उल्लेख किया गया था। हालाँकि उनकी शक्ति की सीमा ओडेड गोल्डरेइच, सिल्वियो मिकाली और एवी विग्डर्सन द्वारा दिखाई गई थी।[6]संपूर्ण एनपी के लिए, और इसे सबसे पहले रसेल इम्पाग्लिआज़ो और मोती युंग द्वारा सभी आईपी तक विस्तारित किया गया था।[11]
एमआईपी
आईपी के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि वेरिफायर को अधिक शक्तिशाली और इतना अव्यवहारिक बनाए बिना इसे और अधिक शक्तिशाली नहीं बनाया जा सकता है। गोल्डवेसर एट अल. अपने 1988 के मल्टी प्रूवर इंटरैक्टिव प्रूफ़्स में इस पर काबू पा लिया: अट्रैक्टिविटी धारणाओं को कैसे दूर करें, जो एमआईपी नामक आईपी के एक प्रकार को परिभाषित करता है जिसमें दो स्वतंत्र प्रोवर्स होते हैं।[12] एक बार जब वेरिफायर ने उन्हें मैसेज भेजना शुरू कर दिया तो दोनों नीतियाँ संवाद नहीं कर सकतीं। जैसे यह बताना आसान है कि अपराधी झूठ बोल रहा है या नहीं, यदि उससे और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो एक दुर्भावनापूर्ण प्रूवर का पता लगाना काफी आसान है जो वेरिफायर को एक स्ट्रिंग को एक्सेप्ट करने के लिए धोखा देने की कोशिश कर रहा है जो लैंग्वेज में नहीं है यदि कोई अन्य प्रूवर है तो यह हो सकता है के साथ दोबारा जांच करें।
वास्तव में, यह इतना हेल्पफुल है कि बाबई, फ़ोर्टनो, और लुंड यह दिखाने में सक्षम थे कि एमआईपी = अगली बार, सभी समस्याओं का वर्ग जो घातीय समय में एक गैर-डिटर्मिनिस्टिक ट्यूरिंग मशीन मशीन द्वारा हल किया जा सकता है, एक बहुत बड़ा वर्ग।[13] NEXPTIME में PSPACE शामिल है, और माना जाता है कि इसमें पूरी तरह से PSPACE शामिल है। दो से अधिक अतिरिक्त सूक्तियों की निरंतर संख्या जोड़ने से किसी और लैंग्वेज की पहचान संभव नहीं हो पाती है। इस परिणाम ने प्रसिद्ध पीसीपी प्रमेय के लिए मार्ग प्रशस्त किया, जिसे इस प्रमेय का एक छोटा संस्करण माना जा सकता है।
एमआईपी में यह सहायक प्रॉपर्टी भी है कि एनपी में प्रत्येक लैंग्वेज के लिए शून्य-ज्ञान प्रूफ को आईपी द्वारा किए जाने वाले एकतरफा कार्यों की धारणा के बिना वर्णित किया जा सकता है। इसका असर संभवतः अटूट क्रिप्टोग्राफ़िक एल्गोरिदम के डिज़ाइन पर पड़ता है।[12]इसके अलावा, एक एमआईपी प्रोटोकॉल केवल निरंतर संख्या में राउंड में आईपी में सभी भाषाओं को पहचान सकता है, और यदि कोई तीसरा प्रूवर जोड़ा जाता है, तो यह NEXPTIME में सभी भाषाओं को निरंतर संख्या में राउंड में पहचान सकता है, जिससे आईपी पर फिर से अपनी शक्ति दिखाई देती है।
यह ज्ञात है कि किसी भी स्थिरांक k के लिए, k प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी सिस्टम को केवल 2 प्रोवर्स और निरंतर संख्या में राउंड के साथ एक समतुल्य सिस्टम में बदला जा सकता है।[14]
पीसीपी
जबकि आईपी के डिजाइनरों ने बाबाई के इंटरैक्टिव प्रूफ सिस्टम के सामान्यीकरण पर विचार किया, वहीं अन्य ने प्रतिबंधों पर विचार किया। एक बहुत ही उपयोगी इंटरैक्टिव प्रूफ सिस्टम पीसीपी(एफ(एन), जी(एन)) है, जो एमए का एक प्रतिबंध है जहां आर्थर केवल एफ का उपयोग कर सकता है (एन) यादृच्छिक बिट्स और केवल मर्लिन द्वारा भेजे गए प्रूफ प्रूफ सर्टिफिकेट के जी(एन) बिट्स की जांच कर सकते हैं (अनिवार्य रूप से यादृच्छिक पहुंच का उपयोग करके)।
विभिन्न पीसीपी कक्षाओं के बारे में आसानी से साबित होने वाले कई परिणाम हैं। , बहुपद-समय मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन सर्टिफिकेट तक पहुंच है, सिर्फ एनपी है। , बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली बहुपद-समय मशीनों का वर्ग सह-आरपी (कम्प्लेक्सिटी) है। अरोरा और सफरा का पहला बड़ा परिणाम यही था PCP(log, log) = NP; दूसरे शब्दों में कहें तो, यदि एनपी प्रोटोकॉल में वेरिफायर केवल चुनने के लिए बाध्य है प्रूफ सर्टिफिकेट के अंशों को देखने के लिए, इससे तब तक कोई फर्क नहीं पड़ेगा जब तक यह उपस्थित है उपयोग करने के लिए यादृच्छिक बिट्स।[15] इसके अलावा, पीसीपी प्रमेय का दावा है कि प्रूफ पहुंच की संख्या को सभी तरह से एक स्थिरांक तक लाया जा सकता है। वह है, .[16] उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम उपस्थित नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब सन्निकटन की कठोरता नामक क्षेत्र में किया जाता है।
यह भी देखें
संदर्भ
- ↑ Goldreich, Oded (2002), Zero-Knowledge twenty years after its invention, ECCC TR02-063.
- ↑ László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.
- ↑ 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
- ↑ Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of ACM STOC'86, pp. 58–68. 1986.
- ↑ 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.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.
- ↑ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
- ↑ Tsuyoshi Ito; Hirotada Kobayashi; John Watrous (2010). "कमजोर त्रुटि सीमाओं के साथ क्वांटम इंटरैक्टिव प्रमाण". arXiv:1012.4427v2 [quant-ph].
- ↑ 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.
- ↑ Aaronson, S. (2010). "QIP = PSPACE breakthrough". Communications of the ACM. 53 (12): 101. doi:10.1145/1859204.1859230. S2CID 34380788.
- ↑ Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [1]
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
पाठ्यपुस्तकें
- Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, March 2009.
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 10.4: Interactive Proof Systems, pp. 354–366.
- Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Section 19.2: Games against nature and interactive protocols, pp. 469–480.
बाहरी संबंध
- Dexter Kozen. Interactive Proofs. CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
- Complexity Zoo:
- Larry Gonick. "Proof Positive?". A comic strip about interactive proof systems.