आईपी (कॉम्प्लेक्सिटी): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 101: Line 101:
* '''फेज 1:''' P, f1(z) के गुणांकों को z में एक पोलिनोमिअल के रूप में भेजता है। जहां V सत्यापित करता है कि f<sub>1</sub> की डिग्री n से कम है और f<sub>0</sub> = f<sub>1</sub>(0) + f<sub>1</sub>(1) है। यदि नहीं तो V अस्वीकृत है और V, F से P को एक यादृच्छिक संख्या r<sub>1</sub> भेजता है।
* '''फेज 1:''' P, f1(z) के गुणांकों को z में एक पोलिनोमिअल के रूप में भेजता है। जहां V सत्यापित करता है कि f<sub>1</sub> की डिग्री n से कम है और f<sub>0</sub> = f<sub>1</sub>(0) + f<sub>1</sub>(1) है। यदि नहीं तो V अस्वीकृत है और V, F से P को एक यादृच्छिक संख्या r<sub>1</sub> भेजता है।
* '''फेज i:''' P, z में पोलिनोमिअल के रूप में <math>f_i(r_1, \dots, r_{i-1}, z)</math> के गुणांक भेजता है। जहां V सत्यापित करता है कि f<sub>i</sub> की डिग्री n से कम है और वह <math>f_{i-1}(r_1, \dots, r_{i-1}) = f_i(r_1, \dots, r_{i-1}, 0) + f_i(r_1, \dots, r_{i-1}, 1)</math> के रूप मे है। यदि नहीं तो V अस्वीकृत है। V, F से P को एक यादृच्छिक संख्या r<sub>i</sub> भेजता है।
* '''फेज i:''' P, z में पोलिनोमिअल के रूप में <math>f_i(r_1, \dots, r_{i-1}, z)</math> के गुणांक भेजता है। जहां V सत्यापित करता है कि f<sub>i</sub> की डिग्री n से कम है और वह <math>f_{i-1}(r_1, \dots, r_{i-1}) = f_i(r_1, \dots, r_{i-1}, 0) + f_i(r_1, \dots, r_{i-1}, 1)</math> के रूप मे है। यदि नहीं तो V अस्वीकृत है। V, F से P को एक यादृच्छिक संख्या r<sub>i</sub> भेजता है।
* '''फेज n+1:''' V मूल्यांकन करता है कि <math>p(r_1, \dots, r_n)</math> की तुलना करने के लिए <math>f_n(r_1, \dots, r_n)</math> यदि समान हैं तो V स्वीकृत है, अथवा V अस्वीकृत है।
* '''फेज n+1:''' V मूल्यांकन करता है कि <math>p(r_1, \dots, r_n)</math> की तुलना करने के लिए <math>f_n(r_1, \dots, r_n)</math> यदि समान हैं तो V स्वीकृत है, अथवा V अस्वीकृत है।


ध्यान दें कि यह एक पब्लिक-कॉइन एल्गोरिथ्म है।
ध्यान दें कि यह एक पब्लिक-कॉइन एल्गोरिथ्म है।
Line 177: Line 177:
* फेज ''k'' + 1: V, <math>p(r_1,\dots,r_m)</math> का मूल्यांकन करता है। फिर यह जांचता है कि क्या <math>p(r_1,\dots,r_m) = f_k(r_1,\dots,r_m)</math> यदि वे बराबर हैं तो V स्वीकृत करता है, अन्यथा V अस्वीकृत कर देता है। यह प्रोटोकॉल विवरण का अंत है.
* फेज ''k'' + 1: V, <math>p(r_1,\dots,r_m)</math> का मूल्यांकन करता है। फिर यह जांचता है कि क्या <math>p(r_1,\dots,r_m) = f_k(r_1,\dots,r_m)</math> यदि वे बराबर हैं तो V स्वीकृत करता है, अन्यथा V अस्वीकृत कर देता है। यह प्रोटोकॉल विवरण का अंत है.


यदि ψ सत्य है तो V तब स्वीकृत करेगा जब P प्रोटोकॉल का पालन करेगा। इसी तरह अगर <math> \tilde{P} </math> एक दुर्भावनापूर्ण कहावत है जो झूठ बोलती है, और यदि ψ गलत है, तो <math> \tilde{P} </math> फेज 0 पर लेटने और f के लिए कुछ मान भेजने की आवश्यकता होगी<sub>0</sub>. यदि फेज I पर, V का मान गलत है <math>f_{i-1}(r_1,\dots)</math> तब <math>f_i(r_1,\dots,0)</math> और <math>f_i(r_1,\dots,1)</math> संभवतः गलत भी होगा, इत्यादि। की संभावना <math> \tilde{P} </math> कुछ यादृच्छिक r पर भाग्यशाली होने के लिए अधिकतम पोलिनोमिअल की डिग्री को फ़ील्ड आकार से विभाजित किया जाता है: <math>n/n^4</math>. प्रोटोकॉल O(n) के माध्यम से चलता है<sup>2</sup>) फेज, तो संभावना है कि <math> \tilde{P} </math> किसी फेज में भाग्यशाली होना ≤ 1/n है। अगर <math>\tilde{P} </math> कभी भी भाग्यशाली नहीं होता है, तो V फेज k+1 पर अस्वीकृत कर देगा।
यदि ψ सत्य है तो V तब स्वीकृत करेगा जब P प्रोटोकॉल का पालन करेगा। इसी तरह अगर <math> \tilde{P} </math> एक दुर्भावनापूर्ण प्रोवर है जो झूठ बोलती है, और यदि ψ गलत है, तो <math> \tilde{P} </math> फेज 0 पर लेटने और f के लिए कुछ मान भेजने की आवश्यकता होगी<sub>0</sub>. यदि फेज I पर, V का मान गलत है <math>f_{i-1}(r_1,\dots)</math> तब <math>f_i(r_1,\dots,0)</math> और <math>f_i(r_1,\dots,1)</math> संभवतः गलत भी होगा, इत्यादि। की संभावना <math> \tilde{P} </math> कुछ यादृच्छिक r पर भाग्यशाली होने के लिए अधिकतम पोलिनोमिअल की डिग्री को फ़ील्ड आकार से विभाजित किया जाता है: <math>n/n^4</math>. प्रोटोकॉल O(n) के माध्यम से चलता है<sup>2</sup>) फेज, तो संभावना है कि <math> \tilde{P} </math> किसी फेज में भाग्यशाली होना ≤ 1/n है। अगर <math>\tilde{P} </math> कभी भी भाग्यशाली नहीं होता है, तो V फेज k+1 पर अस्वीकृत कर देगा।


चूंकि अब हमने दिखाया है कि <code>IP ⊆ PSPACE</code> और <code>'''PSPACE''' ⊆ '''IP'''</code>हम इच्छानुसार यह निष्कर्ष निकाल सकते हैं कि <code>IP = PSPACE</code> इसके अलावा, हमने दिखाया है कि किसी भी आईपी एल्गोरिदम को सार्वजनिक-कॉइन माना जा सकता है, क्योंकि पीएसपीएसीई से आईपी में कमी में यह संपत्ति है।  
चूंकि अब हमने दिखाया है कि <code>IP ⊆ PSPACE</code> और <code>'''PSPACE''' ⊆ '''IP'''</code>हम इच्छानुसार यह निष्कर्ष निकाल सकते हैं कि <code>IP = PSPACE</code> इसके अलावा, हमने दिखाया है कि किसी भी आईपी एल्गोरिदम को सार्वजनिक-कॉइन माना जा सकता है, क्योंकि पीएसपीएसीई से आईपी में कमी में यह संपत्ति है।  


== वेरिएंट ==
== वेरिएंट ==
आईपी ​​के कई प्रकार हैं जो इंटरैक्टिव प्रूफ सिस्टम की परिभाषा को थोड़ा संशोधित करते हैं। हम यहां कुछ बेहतर ज्ञात लोगों का सारांश प्रस्तुत कर रहे हैं।
आईपी ​​के कई वेरिएंट हैं जो इंटरैक्टिव प्रूफ सिस्टम की परिभाषा को अपेक्षाकृत संशोधित करते हैं, जिनमे से कुछ ज्ञात वेरिएंट निम्नलिखित हैं।


=== डीआईपी ===
=== डीआईपी ===
{{main|इंटरैक्टिव प्रूफ सिस्टम}}
{{main|इंटरैक्टिव प्रूफ सिस्टम}}


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


=== उत्तम पूर्णता ===
=== परफेक्ट कॉम्प्लेटनेस ===
आईपी ​​की एक समतुल्य परिभाषा इस शर्त को प्रतिस्थापित करती है कि इंटरेक्शन भाषा में स्ट्रिंग्स पर उच्च संभावना के साथ सफल होता है, इस आवश्यकता के साथ कि यह हमेशा सफल होता है:
आईपी ​​की एक समतुल्य परिभाषा इस शर्त को प्रतिस्थापित करती है कि इंटरेक्शन भाषा में स्ट्रिंग्स पर उच्च संभावना के साथ सफल होता है, इस आवश्यकता के साथ कि यह सदैव सफल होता है:


:<math>w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accepts }w] = 1</math>
:<math>w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accepts }w] = 1</math>
"संपूर्ण पूर्णता" का यह स्पष्ट रूप से मजबूत मानदंड कॉम्प्लेक्सिटी वर्ग आईपी को नहीं बदलता है, क्योंकि इंटरैक्टिव प्रूफ सिस्टम वाली किसी भी भाषा को पूर्ण पूर्णता के साथ एक इंटरैक्टिव प्रूफ सिस्टम दिया जा सकता है।<ref>{{cite journal | author = Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis | year = 1989 | title = इंटरएक्टिव प्रूफ सिस्टम में पूर्णता और सुदृढ़ता पर| journal = Advances in Computing Research: A Research Annual | volume = 5 | pages = 429–442 | citeseerx = 10.1.1.39.9412 }}</ref>
परफेक्ट कॉम्प्लेटनेस स्पष्ट रूप से जटिल मानदंड कॉम्प्लेक्सिटी क्लास मे आईपी को परिवर्तित नहीं करता है क्योंकि इंटरैक्टिव प्रूफ सिस्टम वाली किसी भी भाषा को परफेक्ट कॉम्प्लेटनेस के साथ एक इंटरैक्टिव प्रूफ सिस्टम दिया जा सकता है।<ref>{{cite journal | author = Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis | year = 1989 | title = इंटरएक्टिव प्रूफ सिस्टम में पूर्णता और सुदृढ़ता पर| journal = Advances in Computing Research: A Research Annual | volume = 5 | pages = 429–442 | citeseerx = 10.1.1.39.9412 }}</ref>
===एमआईपी===
===एमआईपी===
{{main|इंटरएक्टिव प्रूफ सिस्टम#एमआईपी
{{main|इंटरएक्टिव प्रूफ सिस्टम#एमआईपी
}}
}}


1988 में, गोल्डवेसर एट अल। आईपी ​​पर आधारित एक और भी अधिक शक्तिशाली इंटरैक्टिव प्रूफ सिस्टम बनाया गया जिसे एमआईपी कहा जाता है जिसमें दो स्वतंत्र प्रोवर्स हैं। एक बार जब सत्यापनकर्ता ने उन्हें संदेश भेजना शुरू कर दिया तो दोनों नीतियाँ संवाद नहीं कर सकतीं। जिस तरह अगर किसी अपराधी से और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो यह बताना आसान होता है कि क्या वह झूठ बोल रहा है, उसी तरह अगर कोई अन्य जासूस है, जिसके साथ वह दोबारा जांच कर सकता है, तो सत्यापनकर्ता को धोखा देने की कोशिश करने वाले दुर्भावनापूर्ण जासूस का पता लगाना काफी आसान है। वास्तव में, यह इतना मददगार है कि बाबई, फ़ोर्टनो और लुंड यह दिखाने में सक्षम थे कि <code>MIP = NEXPTIME</code> डिग्रीीय समय में एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] द्वारा हल की जाने वाली सभी समस्याओं का वर्ग, एक बहुत बड़ा वर्ग। इसके अलावा, एनपी की सभी भाषाओं में बिना किसी अतिरिक्त धारणा के एमआईपी प्रणाली में शून्य-ज्ञान प्रमाण हैं; यह केवल एकतरफ़ा कार्यों के अस्तित्व को मानने वाले आईपी के लिए जाना जाता है।
1988 में गोल्डवेसर आईपी ​​पर आधारित एक और भी अधिक प्रभावी इंटरैक्टिव प्रूफ सिस्टम बनाया गया था जिसे एमआईपी कहा जाता है जिसमें दो स्वतंत्र प्रोवर होते हैं। एक बार जब सत्यापनकर्ता उन्हें संदेश भेजना प्रारम्भ कर देता है तब दोनों प्रोवर संचार नहीं कर सकते है। इस प्रकार यदि किसी अपराधी से और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो यह बताना आसान होता है कि क्या वह झूठ बोल रहा है उसी प्रकार यदि कोई अन्य प्रोवर है, जिसके साथ वह दोबारा जांच कर सकता है, तो सत्यापनकर्ता को डिटेक्ट मॉलिसियस का पता लगाना अपेक्षाकृत आसान होता है। वास्तव में यह इतना लाभदायक है कि बाबई, फ़ोर्टनो और लुंड यह दिखाने में सक्षम थे कि <code>MIP = NEXPTIME</code> समय में एक [[गैर-नियतात्मक ट्यूरिंग मशीन|नॉन-डेटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल की जाने वाली सभी समस्याओं की क्लास एक बहुत बड़ी क्लास के अतिरिक्त एनपी की सभी भाषाओं में बिना किसी अतिरिक्त पुर्वानुमान के एमआईपी सिस्टम में शून्य प्रमाण हैं। यह केवल एकल फंक्शन के अस्तित्व को मानने वाले आईपी के लिए जाना जाता है।


===आईपीपी===
===आईपीपी===
आईपीपी (अनबाउंडेड आईपी) आईपी का एक प्रकार है जहां हम बीपीपी सत्यापनकर्ता को पीपी सत्यापनकर्ता द्वारा प्रतिस्थापित करते हैं। अधिक सटीक रूप से, हम पूर्णता और सुदृढ़ता स्थितियों को निम्नानुसार संशोधित करते हैं:
आईपीपी (अनबाउंडेड आईपी) आईपी का एक वेरिएंट है जहां हम बीपीपी सत्यापनकर्ता को पीपी सत्यापनकर्ता द्वारा प्रतिस्थापित करते हैं। सामान्यतः हम इसको कॉम्प्लेटनेस और साउंडनेस की स्थितियों के निम्नानुसार संशोधित करते हैं:


* पूर्णता: यदि कोई स्ट्रिंग भाषा में है, तो ईमानदार सत्यापनकर्ता कम से कम 1/2 संभावना के साथ एक ईमानदार सूचक द्वारा इस तथ्य के बारे में आश्वस्त होगा।
* '''कॉम्प्लेटनेस:''' यदि कोई स्ट्रिंग भाषा में है तो सत्यापनकर्ता को इस तथ्य के विषय में कम से कम 1/2 संभावना वाले एक ऑनेस्ट सूचक द्वारा कॉन्विंस्ड किया जाता है।
* सुदृढ़ता: यदि स्ट्रिंग भाषा में नहीं है, तो कोई भी कहावत ईमानदार सत्यापनकर्ता को यह विश्वास नहीं दिला सकती है कि यह भाषा में है, सिवाय 1/2 से कम संभावना के।
* '''साउंडनेस:''' यदि स्ट्रिंग भाषा में नहीं है, तो 1/2 से कम संभावना को छोड़कर कोई भी प्रोवर ऑनेस्ट सत्यापनकर्ता को यह विश्वास नहीं दे सकता है कि यह भाषा में है।


हालाँकि IPP भी <code>PSPACE</code> के बराबर है, IPP प्रोटोकॉल, Oracles के संबंध में IP से काफी भिन्न व्यवहार करता है <code>IPP=PSPACE</code> सभी Oracles के संबंध में, जबकि<code>IP ≠ PSPACE</code> लगभग सभी Oracles के संबंध में।<ref>R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. [http://citeseer.ist.psu.edu/chang97random.html The random oracle hypothesis is false]. ''Journal of Computer and System Sciences'', 49(1):24-39. 1994.</ref>  
हालाँकि आईपीपी भी <code>PSPACE</code> के बराबर है, आईपीपी प्रोटोकॉल ओरेकल के संबंध में आईपी से अपेक्षाकृत भिन्न है। सभी <code>IPP=PSPACE</code> ओरेकल के संबंध में<code>IP ≠ PSPACE</code> के लगभग सभी प्रोटोकॉल ओरेकल के संबंध में है।<ref>R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. [http://citeseer.ist.psu.edu/chang97random.html The random oracle hypothesis is false]. ''Journal of Computer and System Sciences'', 49(1):24-39. 1994.</ref>  
===क्यूआईपी===
===क्यूआईपी===
{{main|क्वांटम इंटरएक्टिव प्रोटोकॉल
{{main|क्वांटम इंटरएक्टिव प्रोटोकॉल
}}
}}


[[क्वांटम इंटरएक्टिव प्रोटोकॉल]] आईपी का एक संस्करण है जो बीपीपी सत्यापनकर्ता को [[BQP|बीक्यूपी]] सत्यापनकर्ता द्वारा प्रतिस्थापित करता है, जहां बीक्यूपी पोलिनोमिअल समय में क्वांटम कंप्यूटर द्वारा हल की जाने वाली समस्याओं का वर्ग है। संदेश क्वैबिट से बने होते हैं। 2009 में, जैन, जी, उपाध्याय और वॉट्रस ने सिद्ध किया कि QIP भी <code>PSPACE</code> के बराबर है<ref>{{cite arXiv|eprint=0907.4737|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4=John Watrous|author-link4=John Watrous (computer scientist)|title=QIP = PSPACE|class=quant-ph|year=2009}}</ref> जिसका अर्थ है कि यह परिवर्तन प्रोटोकॉल को कोई अतिरिक्त शक्ति नहीं देता है। यह किताएव और वॉट्रस के पिछले परिणाम को समाहित करता है कि QIP [[EXPTIME]] में समाहित है क्योंकि <code>QIP = QIP</code> इसलिए तीन से अधिक राउंड कभी भी आवश्यक नहीं होते हैं।<ref>A. Kitaev and J. Watrous. [https://cs.uwaterloo.ca/~watrous/Papers/QuantumInteractiveProofs.pdf Parallelization, amplification, and exponential time simulation of quantum interactive proof systems]. ''Proceedings of the 32nd ACM Symposium on Theory of Computing'', pp. 608-617. 2000.</ref>
[[क्वांटम इंटरएक्टिव प्रोटोकॉल]] आईपी का एक संस्करण है जो बीपीपी सत्यापनकर्ता को [[BQP|बीक्यूपी]] सत्यापनकर्ता द्वारा प्रतिस्थापित करता है, जहां बीक्यूपी पोलिनोमिअल टाइम में क्वांटम कंप्यूटर द्वारा हल की जाने वाली समस्याओं की क्लास है। संदेश क्वैबिट से बने होते हैं। 2009 में जैन जी उपाध्याय और वॉट्रस ने सिद्ध किया कि <code>QIP</code> भी <code>PSPACE</code> के बराबर है<ref>{{cite arXiv|eprint=0907.4737|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4=John Watrous|author-link4=John Watrous (computer scientist)|title=QIP = PSPACE|class=quant-ph|year=2009}}</ref> जिसका अर्थ है कि यह परिवर्तन प्रोटोकॉल को कोई अतिरिक्त पावर नहीं देता है। यह किताएव और वॉट्रस के पिछले परिणाम को समाहित करता है कि क्यूआईपी [[EXPTIME|ऍक्स्पटीआईएमई]] में समाहित है क्योंकि <code>QIP = QIP</code> होता है। इसलिए इसे तीन से अधिक राउंड कभी भी आवश्यक नहीं होते हैं।<ref>A. Kitaev and J. Watrous. [https://cs.uwaterloo.ca/~watrous/Papers/QuantumInteractiveProofs.pdf Parallelization, amplification, and exponential time simulation of quantum interactive proof systems]. ''Proceedings of the 32nd ACM Symposium on Theory of Computing'', pp. 608-617. 2000.</ref>
===compIP===
===कॉम्पआईपी ===
जबकि आईपीपी और क्यूआईपी सत्यापनकर्ता को अधिक शक्ति देते हैं, एक कॉम्पआईपी सिस्टम (प्रतिस्पर्धी आईपी प्रूफ सिस्टम) पूर्णता की स्थिति को एक तरह से कमजोर कर देता है जिससे प्रोवर कमजोर हो जाता है:
सामान्यतः आईपीपी और क्यूआईपी सत्यापनकर्ता को अधिक पावर देते हैं। एक कॉम्पआईपी सिस्टम (प्रतिस्पर्धी आईपी प्रूफ सिस्टम) कॉम्प्लेटनेस की स्थिति को एक प्रकार से कमजोर (वीक) कर देता है जिससे प्रोवर वीक हो जाता है:


* पूर्णता: यदि कोई स्ट्रिंग भाषा एल में है, तो ईमानदार सत्यापनकर्ता को कम से कम 2/3 संभावना के साथ एक ईमानदार कहावत द्वारा इस तथ्य के बारे में आश्वस्त किया जाएगा। इसके अलावा, भाषा एल के लिए दैवज्ञ तक पहुंच दिए जाने पर कहावत संभाव्य पोलिनोमिअल समय में ऐसा करेगी।
* '''कॉम्प्लेटनेस:''' यदि कोई स्ट्रिंग भाषा एल में है, तो सत्यापनकर्ता को कम से कम 2/3 संभावना के साथ एक प्रोवर द्वारा इस तथ्य के विषय में कॉन्विंस्ड किया जाता है। इसके अतिरिक्त भाषा एल के लिए ओरेकल द्वारा एक्सेस दिए जाने पर प्रोवर प्रॉबबिलिस्टिक पोलिनोमिअल टाइम निम्नलिखित हो सकता है:


अनिवार्य रूप से, यह कहावत को भाषा के लिए दैवज्ञ तक पहुंच के साथ एक बीपीपी मशीन बनाता है, लेकिन केवल पूर्णता के मामले में, सुदृढ़ता के मामले में नहीं। अवधारणा यह है कि यदि कोई भाषा कॉम्पआईपी में है, तो अंतःक्रियात्मक रूप से इसे सिद्ध करना कुछ अर्थों में इसे तय करने जितना आसान है। दैवज्ञ के साथ, सूचक समस्या को आसानी से हल कर सकता है, लेकिन इसकी सीमित शक्ति किसी भी चीज़ के सत्यापनकर्ता को समझाना अधिक कठिन बना देती है। वास्तव में, कंपआईपी में एनपी होने की जानकारी नहीं है या माना जाता है कि इसमें एनपी शामिल है।
अनिवार्य रूप से यह प्रोवर को भाषा के लिए ओरेकल एक्सेस के साथ एक बीपीपी मशीन बनाता है, लेकिन केवल कॉम्प्लेटनेस की स्थिति मे साउंडनेस की अवधारणा यह है कि यदि कोई भाषा कॉम्पआईपी में है, तो इंटरैक्टिव रूप से इसे सिद्ध करना कुछ अर्थों में इसे तय करने जितना आसान है। ओरेकल के साथ सूचक समस्या को आसानी से हल किया जा सकता है लेकिन इसकी सीमित पावर किसी भी ऑब्जेक्ट के सत्यापनकर्ता को समझाना अधिक जटिल बना देती है। वास्तव में कंपआईपी में एनपी होने की जानकारी नहीं होती है। यह माना जाता है कि इसमें एनपी सम्मिलित है।


दूसरी ओर, ऐसी प्रणाली कठिन समझी जाने वाली कुछ समस्याओं का समाधान कर सकती है। कुछ हद तक विरोधाभासी रूप से, हालांकि ऐसा माना जाता है कि ऐसी प्रणाली सभी एनपी को हल करने में सक्षम नहीं है, यह स्व-रिड्यूसिबिलिटी के कारण सभी एनपी-पूर्ण समस्याओं को आसानी से हल कर सकती है। यह इस तथ्य से उपजा है कि यदि भाषा एल एनपी-हार्ड नहीं है, तो कहावत की शक्ति काफी हद तक सीमित है (क्योंकि यह अब अपने ओरेकल के साथ सभी एनपी समस्याओं का समाधान नहीं कर सकती है)।इसके अतिरिक्त, [[ग्राफ समरूपता समस्या|ग्राफ नॉनआइसोमोर्फिज्म समस्या]] (जो आईपी में एक शास्त्रीय समस्या है) भी कॉम्पआईपी में है, क्योंकि प्रोवर को एकमात्र कठिन ऑपरेशन आइसोमोर्फिज्म परीक्षण करना होता है, जिसे हल करने के लिए वह ओरेकल का उपयोग कर सकता है। द्विडिग्री गैर-अवशेषता और ग्राफ समरूपता भी कॉम्पआईपी में हैं।<ref>Shafi Goldwasser and [[Mihir Bellare]]. [http://www.cs.ucsd.edu/users/mihir/papers/compip.pdf The Complexity of Decision versus Search]. ''SIAM Journal on Computing'', Volume 23, No. 1. February 1994.</ref> ध्यान दें, द्विडिग्री गैर-अवशेषता (क्यूएनआर) संभवतः ग्राफ समरूपता की तुलना में एक आसान समस्या है क्योंकि क्यूएनआर यूपी प्रतिच्छेद सह-यूपी में है।<ref>{{cite journal |vauthors=Cai JY, Threlfall RA | year = 2004 | title = द्विघात अवशिष्टता और '''यूपी''' पर एक नोट| journal = Information Processing Letters | volume = 92 | issue = 3| pages = 127–131 | doi=10.1016/j.ipl.2004.06.015| citeseerx = 10.1.1.409.1830 }}</ref>
'''दूसरी ओर, ऐसी प्रणाली कठिन समझी जा'''ने वाली कुछ समस्याओं का समाधान कर सकती है। कुछ हद तक विरोधाभासी रूप से, हालांकि ऐसा माना जाता है कि ऐसी प्रणाली सभी एनपी को हल करने में सक्षम नहीं है, यह स्व-रिड्यूसिबिलिटी के कारण सभी एनपी-पूर्ण समस्याओं को आसानी से हल कर सकती है। यह इस तथ्य से उपजा है कि यदि भाषा एल एनपी-हार्ड नहीं है, तो प्रोवर की पावर काफी हद तक सीमित है (क्योंकि यह अब अपने ओरेकल के साथ सभी एनपी समस्याओं का समाधान नहीं कर सकती है)।इसके अतिरिक्त, [[ग्राफ समरूपता समस्या|ग्राफ नॉनआइसोमोर्फिज्म समस्या]] (जो आईपी में एक शास्त्रीय समस्या है) भी कॉम्पआईपी में है, क्योंकि प्रोवर को एकमात्र कठिन ऑपरेशन आइसोमोर्फिज्म परीक्षण करना होता है, जिसे हल करने के लिए वह ओरेकल का उपयोग कर सकता है। द्विडिग्री गैर-अवशेषता और ग्राफ समरूपता भी कॉम्पआईपी में हैं।<ref>Shafi Goldwasser and [[Mihir Bellare]]. [http://www.cs.ucsd.edu/users/mihir/papers/compip.pdf The Complexity of Decision versus Search]. ''SIAM Journal on Computing'', Volume 23, No. 1. February 1994.</ref> ध्यान दें, द्विडिग्री गैर-अवशेषता (क्यूएनआर) संभवतः ग्राफ समरूपता की तुलना में एक आसान समस्या है क्योंकि क्यूएनआर यूपी प्रतिच्छेद सह-यूपी में है।<ref>{{cite journal |vauthors=Cai JY, Threlfall RA | year = 2004 | title = द्विघात अवशिष्टता और '''यूपी''' पर एक नोट| journal = Information Processing Letters | volume = 92 | issue = 3| pages = 127–131 | doi=10.1016/j.ipl.2004.06.015| citeseerx = 10.1.1.409.1830 }}</ref>
== टिप्पणियाँ ==
== टिप्पणियाँ ==
<!--See http://en.wikipedia.org/wiki/Wikipedia:Footnotes for an explanation of how to generate footnotes using the <ref(erences/)> tags-->
<!--See http://en.wikipedia.org/wiki/Wikipedia:Footnotes for an explanation of how to generate footnotes using the <ref(erences/)> tags-->

Revision as of 09:20, 7 August 2023

कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत में क्लास आईपी (इंटरैक्टिव-प्रूफ) एक इंटरैक्टिव प्रूफ सिस्टम (आईपीएस) द्वारा हल की जाने वाली समस्याओं की क्लास है। यह क्लास पीएसपीएसीई के बराबर है। जिसके परिणाम को पेपर की एक सीरीज (श्रेणी) में स्थापित किया गया था। इसके प्रथम प्रकाशन को कार्लॉफ, फ़ोर्टनो और निसान द्वारा प्रदर्शित किया गया था जिसमे सीओ-एनपी के पास कई प्रोवर इंटरैक्टिव प्रमाण थे, और दूसरे प्रकाशन को शमीर द्वारा IP = PSPACE मे स्थापित करने के लिए कई तकनीकों को नियोजित किया गया था।[1][2]

इंटरैक्टिव प्रूफ सिस्टम की अवधारणा पहली बार 1985 में शफ़ी गोल्डवेसर, सिल्वियो मिकाली और चार्ल्स रैकॉफ़ द्वारा प्रस्तुत की गई थी। इंटरैक्टिव प्रूफ सिस्टम में दो प्रोवर और P मशीनें होती हैं जो एक प्रमाण प्रस्तुत को प्रस्तुत करती है कि एक दी गई स्ट्रिंग n इसकी क्लास है जो भाषा और सत्यापनकर्ता (वेरीफायर) V का परीक्षण करती है कि प्रस्तुत प्रमाण सही है। प्रोवर को गणना और स्टोरेज (भंडारण) में अनंत माना जाता है, जबकि सत्यापनकर्ता एक यादृच्छिक बिट स्ट्रिंग के साथ एक प्रॉबबिलिस्टिक पोलिनोमिअल टाइम मशीन है जिसकी लंबाई n के आकार पर पोलिनोमिअल होती है। ये दोनों मशीनें संदेशों की एक पोलिनोमिअल संख्या p(n) का स्थानांतरण करती हैं और एक बार स्थानांतरण पूर्ण हो जाने पर सत्यापनकर्ता को यह तय करना होता है कि n भाषा में है या n भाषा में नही है जिसमे त्रुटि की केवल 1/3 की संभावना होती है। इसीलिए बीपीपी में कोई भी भाषा आईपी के रूप मे हो सकती है। जिसमे सत्यापनकर्ता केवल प्रोवर को स्थानांतरित करके स्वयं निर्णय ले सकता है।

एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।

परिभाषा

एक भाषा L आईपी से संबंधित है यदि V, P मे सम्मिलित है जैसे कि सभी Q, w के लिए निम्न है:

लास्ज़लो बाबई द्वारा प्रस्तुत आर्थर-मर्लिन प्रोटोकॉल में समान होता है यदि इसके स्थानांतरण के समय की संख्या पोलिनोमिअल के अतिरिक्त एक स्थिरांक से संबद्ध होती है।

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

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

आईपी = पीएसपीएसीई

सामान्यतः प्रमाण को दो IP ⊆ PSPACE और PSPACE ⊆ IP भागों में विभाजित किया जा सकता है।

आईपी ⊆ पीएसपीएसीई

IP ⊆ PSPACE को प्रदर्शित करने के लिए हम एक पोलिनोमिअल स्पेस मशीन द्वारा एक इंटरैक्टिव प्रूफ सिस्टम का अनुकरण प्रस्तुत करते हैं, जिससे हम निम्नलिखित को परिभाषित कर सकते हैं:

प्रत्येक 0 ≤ j ≤ p और प्रत्येक संदेश स्टोरेज Mj के लिए हम फ़ंक्शन NMj को प्रेरक रूप से परिभाषित करते हैं:

जहाँ:

जहां Prr लंबाई p की यादृच्छिक स्ट्रिंग r पर ली गई प्रोबेबिलिटी है। सामान्यतः यह NMj+1 का औसत है जो इस प्रोबेबिलिटी (संभाव्यता) पर आधारित है कि सत्यापनकर्ता ने संदेश mj+1 भेजा है। यदि M0 को रिक्त संदेश अनुक्रम मानें तब हम प्रदर्शित कर सकते हैं कि NM0 की गणना पोलिनोमिअल-स्पेस में की जा सकती है और NM0 = Pr मे [V, w] को स्वीकृत किया जा सकता है। सबसे पहले NM0 की गणना करने के लिए एक एल्गोरिदम प्रत्येक j और Mj के लिए NMj मानों की पुनरावर्ती करके गणना कर सकता है। चूँकि रिकर्शन p है जिसके लिए केवल पोलिनोमिअल क्लास आवश्यक होती है। दूसरी आवश्यकता यह है कि हमें NM0 = Pr मे [V, w] की आवश्यकता होती है। जिससे यह निर्धारित किया जा सके कि आवश्यक मान w, A में सम्मिलित है या नहीं सम्मिलित है। इसे सिद्ध करने के लिए हम प्रूवर का उपयोग इस प्रकार करते हैं।

सामान्यतः हमें यह दिखाना होगा कि 0 ≤ j ≤ p प्रत्येक Mj के लिए NMj = Pr, V, Mj से प्रारंभ करके w को स्वीकृत करता है और हम j पर इंडक्शन का उपयोग कर सकते है। जहां j = p के लिए सिद्ध करना है। फिर हम p से 0 तक जाने के लिए इंडक्शन का उपयोग कर सकते हैं। j = p का आधार अपेक्षाकृत सरल होता है। चूंकि mp या तो एक्सेप्ट या रेजेक्ट है, यदि mp एक्सेप्ट है, तो NMp को 1 के रूप में परिभाषित किया जा सकता है और यदि Pr[V, Mj] = 1 है तब संदेश स्ट्रीम एक्सेप्ट (स्वीकृत) को इंगित करता है। इस प्रकार सिद्ध है कि mp अस्वीकृत है। इंडुक्टिव परिकल्पना के लिए हम मानते हैं कि कुछ j+1 ≤ p और किसी भी संदेश अनुक्रम Mj+1 के लिए Mj+1, NMj+1 = , j और किसी भी संदेश अनुक्रम Mj के लिए परिकल्पना को सिद्ध किया जा सकता है।

NMj की परिभाषा के अनुसार यदि j सम है तो mj+1, V से P तक एक संदेश है:

तब इंडुक्टिव परिकल्पना द्वारा हम कह सकते हैं कि यह बराबर है:

अंत में, परिभाषा के अनुसार हम देख सकते हैं कि यह के बराबर है।

परिभाषा के अनुसार यदि j विषम है, तो mj+1 P से V तक एक संदेश है:

तब इंडुक्टिव परिकल्पना द्वारा यह बराबर होता है:

यह के बराबर है:

क्योंकि दाहिनी ओर का सूचक बायीं ओर की अभिव्यक्ति को अधिकतम करने के लिए संदेश mj+1 भेज सकता है:

चूँकि प्रोवर उसी संदेश को भेजने के अतिरिक्त कुछ नहीं कर सकता है। इस प्रकार यह मानता है कि क्या i सम है या विषम है सामान्यतः इसका प्रमाण है कि IP ⊆ PSPACE पूर्ण है।

यहां हमने एक पोलिनोमिअल स्पेस मशीन का निर्माण किया है जो भाषा A में एक विशेष स्ट्रिंग W के लिए सर्वश्रेष्ठ प्रोवर P का उपयोग करती है। हम यादृच्छिक इनपुट बिट्स के साथ प्रोवर के स्थान पर इस सर्वश्रेष्ठ प्रोवर का उपयोग करते हैं क्योंकि हम यादृच्छिक इनपुट बिट्स के प्रत्येक पोलिनोमिअल समूह का उपयोग करने मे सक्षम हैं। चूंकि हमने एक पोलिनोमिअल स्पेस मशीन के साथ एक इंटरैक्टिव प्रूफ सिस्टम का अनुकरण किया है। इसलिए हम आवश्यकता अनुसार IP ⊆ PSPACE को प्रदर्शित कर सकते हैं।

पीएसपीएसीई ⊆ आईपी

PSPACE ⊆ IP को सिद्ध करने के लिए उपयोग की जाने वाली तकनीक को स्पष्ट करने के लिए, हम पहले एक वीकर सिद्धान्त को सिद्ध करेंगे, जिसे लुंड सैट ∈ आईपी द्वारा सिद्ध किया गया था। फिर इस प्रमाण से अवधारणाओं का उपयोग करके हम इसे TQBF ∈ IP दिखाने के लिए TQBF ∈ PSPACEऔर TQBF ∈ IP विस्तारित करेंगे। चूँकि PSPACE ⊆ IP है।

एसएटी आईपी

हम यह दिखाकर प्रारम्भ करते हैं कि एसएटी आईपी में है, जहां:

ध्यान दें कि यह एसएटी की सामान्य परिभाषा से अलग है, क्योंकि यह एक फ़ंक्शन के अतिरिक्त एक निर्णय समस्या है।

सबसे पहले हम n वेरिएबल को φ(b1, ..., bn) के साथ बूलियन सूत्र को एक पोलिनोमिअल pφ(x1, ..., xn) में मैप करने के लिए अंकगणित का उपयोग करते हैं। जहां pφ उस pφ में φ की प्रतिलिपि बनाता है यदि φ सत्य है तो 1 और 0 अन्यथा pφ के वेरिएबल को बूलियन मान निर्दिष्ट किया जा सकता है। φ में उपयोग किए गए बूलियन ऑपरेटर (संक्रियक) ∨, ∧ और ¬ को φ ऑपरेटरों मे प्रतिस्थापित करके pφ में सिम्युलेटेड किया गया है जैसा कि नीचे दी गई तालिका में दिखाया गया है।

ab ab
ab ab := 1 − (1 − a)(1 − b)
¬a 1 − a
बूलियन सूत्र φ(b1, ..., bn) को पोलिनोमिअल pφ(x1, ..., xn) में परिवर्तित करने के लिए अंकगणितीय नियम

उदाहरण के लिए φ = a ∧ (b ∨ ¬c) को निम्नानुसार पोलिनोमिअल में परिवर्तित किया जा सकता है:

ऑपरेटर ab और a ∗ b में से प्रत्येक का परिणाम एक पोलिनोमिअल में होता है, जिसकी डिग्री a और b के लिए पोलिनोमिअल की डिग्री के योग के बराबर होती है। इसलिए किसी भी वेरिएबल की डिग्री अधिकतम φ की लंबाई होती है।

माना कि F एक परिमित क्षेत्र है जिसका अनुक्रम q > 2n है, साथ ही माना कि q का मान कम से कम 1000 है और प्रत्येक 0 ≤ i ≤ n के लिए F पर पैरामीटर वाले एक फ़ंक्शन φ को परिभाषित किया जाता है और 0 ≤ i के लिए F में एक एकल वेरिएबल ai है जहां n और हैं:

ध्यान दें कि f0 का मान φ के संतोषजनक असाइनमेंट की संख्या है। f0 एक शून्य फ़ंक्शन है, जिसमें कोई वेरिएबल नहीं है।

एसएटी का प्रोटोकॉल इस प्रकार कार्य करता है:

  • फेज 0: प्रूवर P एक अभाज्य संख्या q > 2n चुनता है और f0 की गणना करता है, फिर यह सत्यापनकर्ता V को q और f0 भेजता है। जहां V जाँच करता है कि q अधिकतम (1000, 2n) से बड़ा अभाज्य है और f0() = k है।
  • फेज 1: P, f1(z) के गुणांकों को z में एक पोलिनोमिअल के रूप में भेजता है। जहां V सत्यापित करता है कि f1 की डिग्री n से कम है और f0 = f1(0) + f1(1) है। यदि नहीं तो V अस्वीकृत है और V, F से P को एक यादृच्छिक संख्या r1 भेजता है।
  • फेज i: P, z में पोलिनोमिअल के रूप में के गुणांक भेजता है। जहां V सत्यापित करता है कि fi की डिग्री n से कम है और वह के रूप मे है। यदि नहीं तो V अस्वीकृत है। V, F से P को एक यादृच्छिक संख्या ri भेजता है।
  • फेज n+1: V मूल्यांकन करता है कि की तुलना करने के लिए यदि समान हैं तो V स्वीकृत है, अथवा V अस्वीकृत है।

ध्यान दें कि यह एक पब्लिक-कॉइन एल्गोरिथ्म है।

यदि φ में k संतोषजनक असाइनमेंट हैं, तो स्पष्ट रूप से V स्वीकृत करेगा। यदि φ में k संतोषजनक कार्य नहीं हैं तो हम मान लेते हैं कि एक प्रोवर है जो V को समझाने का प्रयास करता है कि φ में k संतोषजनक कार्य हैं। हम दिखाते हैं कि यह केवल अपेक्षाकृत कम संभावना के साथ ही किया जा सकता है।

फेज 0 में V को अस्वीकृत करने से रोकने के लिए को एक गलत मान भेजना होगा। फिर, फेज 1 में को मान के साथ एक गलत पोलिनोमिअल भेजना होगा। तब V, P को भेजने के लिए एक यादृच्छिक मान r1 चुनता है:

इसका कारण यह है कि डिग्री के एकल वेरिएबल वाले पोलिनोमिअल में अधिकतम d के मूल d से अधिक नहीं हो सकते हैं। जब तक कि इसका मूल्यांकन 0 न हो। अतः डिग्री के एक ही वेरिएबल में अधिकतम d वाले कोई भी दो पोलिनोमिअल केवल d स्थानों पर ही समान हो सकते हैं। चूंकि |F| > 2n r1 के इन मानों में से एक होने की संभावना अधिकतम है यदि n > 10 या अधिकतम (n/1000) ≤ (n/n3) यदि n ≤ 10 है।

इस विचार को अन्य फेजों के लिए सामान्यीकृत करना हमारे पास प्रत्येक: मान 1 ≤ i ≤ n के लिए है:

फिर F से यादृच्छिक रूप से चुने गए ri के लिए,
वहाँ n फेज हैं, इसलिए संभावना है कि सत्य है क्योंकि V किसी फेज में एक सुविधाजनक ri का चयन करता है जो अधिकतम 1/n है। इसलिए कोई भी सूचक सत्यापनकर्ता को 1/n से अधिक संभावना के साथ स्वीकृत करने के लिए बाध्य नहीं कर सकता है। हम परिभाषा से यह भी देख सकते हैं कि सत्यापनकर्ता V संभाव्य पोलिनोमिअल समय में कार्य करता है। इस प्रकार SAT ∈ IP है।

टीक्यूबीएफ आईपी

यह दिखाने के लिए कि पीएसपीएसीई आईपी का एक उपसमूह है सामान्यतः इसके लिए हमें एक पीएसपीएसीई पूर्ण समस्या चुननी होगी और दिखाना होगा कि यह आईपी में है। एक बार जब हम इसे दिखा देते हैं, तो यह स्पष्ट हो जाता है कि PSPACE ⊆ IP यहां प्रदर्शित प्रमाण तकनीक का श्रेय आदि शमीर को दिया जाता है।

हम जानते हैं कि TQBF PSPACE-Complete में है। तब माना कि ψ एक परिमाणित बूलियन एक्सप्रेशन है:

जहां φ एक सीएनएफ सूत्र है। तब क्यूई एक परिमाणक है या तो ∃ या ∀ अब φ पिछले प्रमाण के समान ही है, लेकिन अब इसमें क्वांटिफायर भी सम्मिलित है:

यहां φ(a1, ..., ai) φ है जिसमें x1 से xi के स्थान पर a1 से ai प्रतिस्थापित किया गया है। इस प्रकार f0 ψ का सत्य मान है। ψ का अंकगणितीय मान निकालने के लिए हमें निम्नलिखित नियमों का उपयोग करना चाहिए:

जबकि पहले हम x * y = 1 − (1 − x)(1 − y) परिभाषित करते थे।

  1. एसएटी में वर्णित विधि का उपयोग करके, हमें एक समस्या का सामना करना पड़ता है जिससे किसी भी φ के लिए परिणामी पोलिनोमिअल की डिग्री प्रत्येक परिमाणक के साथ दोगुनी हो सकती है। इसे रोकने के लिए हमें एक नया रिडक्शन ऑपरेटर R प्रस्तुत करना होगा जो बूलियन इनपुट पर उनके परिणाम को परिवर्तित किए बिना पोलिनोमिअल की डिग्री को कम कर देता है।

तो अब इससे पहले कि हम की एक नई अभिव्यक्ति प्रस्तुत करते हैं:

या दूसरे प्रकार से,

अब प्रत्येक i ≤ k के लिए हम फ़ंक्शन fi को परिभाषित करते हैं। और को पोलिनोमिअल p(x1, ..., xm) के रूप में भी परिभाषित करते हैं जिससे φ को अंकगणितीय रूप मे प्राप्त किया जाता है। फिर पोलिनोमिअल की डिग्री को अपेक्षाकृत कम रखने के लिए हम fi को fi+1 के रूप में परिभाषित करते हैं:

ब हम देख सकते हैं कि कमी संक्रिया R, बहुपद की डिग्री को नहीं बदलती है। यह भी देखना महत्वपूर्ण है कि आरएक्स ऑपरेशन बूलियन इनपुट पर फ़ंक्शन के मान को नहीं बदलता है। तो f0 अभी भी ψ का सत्य मान है, लेकिन Rx मान एक परिणाम उत्पन्न करता है जो x में रैखिक है। इसके अतिरिक्त किसी भी के बाद हम को जोड़ते हैं। को ψ′ में अंकगणित करने के बाद डिग्री को 1 तक कम करने के लिए।

अब प्रोटोकॉल का वर्णन करते हैं। यदि n ψ की लंबाई है, तो प्रोटोकॉल में सभी अंकगणितीय ऑपरेशन कम से कम n4 आकार के क्षेत्र पर होते हैं जहां n ψ की लंबाई है।

  • फेज़ 0: P → V: P, V को f0 भेजता है। V जाँच करता है कि f0= 1 है और यदि नहीं है तो अस्वीकार कर देता है।
  • फेज़ 1: P → V: P, V को f1(z) भेजता है। V, f1(0) और f1(1) का मूल्यांकन करने के लिए गुणांक का उपयोग करता है। फिर यह जाँचता है कि बहुपद की डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:
यदि दोनों में से कोई भी विफल रहता है तो अस्वीकृत करें।
  • चरण i: P → V: P, z में बहुपद के रूप में भेजता है। के लिए पहले से निर्धारित यादृच्छिक मानों को दर्शाता है

V मूल्यांकन के लिए गुणांकों का उपयोग करता है और . फिर यह जाँचता है कि पोलिनोमिअल डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:

यदि दोनों में से कोई भी विफल रहता है तो अस्वीकृत कर दें।

वी → पी: वी एफ में एक यादृच्छिक आर चुनता है और इसे पी को भेजता है। (यदि तब यह r पिछले r को प्रतिस्थापित कर देता है)।

फेज i +1 पर जाएं जहां P को V को इस बात के लिए राजी करना होगा सही है।

  • फेज k + 1: V, का मूल्यांकन करता है। फिर यह जांचता है कि क्या यदि वे बराबर हैं तो V स्वीकृत करता है, अन्यथा V अस्वीकृत कर देता है। यह प्रोटोकॉल विवरण का अंत है.

यदि ψ सत्य है तो V तब स्वीकृत करेगा जब P प्रोटोकॉल का पालन करेगा। इसी तरह अगर एक दुर्भावनापूर्ण प्रोवर है जो झूठ बोलती है, और यदि ψ गलत है, तो फेज 0 पर लेटने और f के लिए कुछ मान भेजने की आवश्यकता होगी0. यदि फेज I पर, V का मान गलत है तब और संभवतः गलत भी होगा, इत्यादि। की संभावना कुछ यादृच्छिक r पर भाग्यशाली होने के लिए अधिकतम पोलिनोमिअल की डिग्री को फ़ील्ड आकार से विभाजित किया जाता है: . प्रोटोकॉल O(n) के माध्यम से चलता है2) फेज, तो संभावना है कि किसी फेज में भाग्यशाली होना ≤ 1/n है। अगर कभी भी भाग्यशाली नहीं होता है, तो V फेज k+1 पर अस्वीकृत कर देगा।

चूंकि अब हमने दिखाया है कि IP ⊆ PSPACE और PSPACEIPहम इच्छानुसार यह निष्कर्ष निकाल सकते हैं कि IP = PSPACE इसके अलावा, हमने दिखाया है कि किसी भी आईपी एल्गोरिदम को सार्वजनिक-कॉइन माना जा सकता है, क्योंकि पीएसपीएसीई से आईपी में कमी में यह संपत्ति है।

वेरिएंट

आईपी ​​के कई वेरिएंट हैं जो इंटरैक्टिव प्रूफ सिस्टम की परिभाषा को अपेक्षाकृत संशोधित करते हैं, जिनमे से कुछ ज्ञात वेरिएंट निम्नलिखित हैं।

डीआईपी

आईपी ​​की क्लास डेटर्मिनिस्टिक इंटरैक्टिव प्रूफ क्लास है, जो आईपी के समान है लेकिन इसमें एक डेटर्मिनिस्टिक सत्यापनकर्ता है अर्थात यह क्लास एनपी के बराबर है।

परफेक्ट कॉम्प्लेटनेस

आईपी ​​की एक समतुल्य परिभाषा इस शर्त को प्रतिस्थापित करती है कि इंटरेक्शन भाषा में स्ट्रिंग्स पर उच्च संभावना के साथ सफल होता है, इस आवश्यकता के साथ कि यह सदैव सफल होता है:

परफेक्ट कॉम्प्लेटनेस स्पष्ट रूप से जटिल मानदंड कॉम्प्लेक्सिटी क्लास मे आईपी को परिवर्तित नहीं करता है क्योंकि इंटरैक्टिव प्रूफ सिस्टम वाली किसी भी भाषा को परफेक्ट कॉम्प्लेटनेस के साथ एक इंटरैक्टिव प्रूफ सिस्टम दिया जा सकता है।[3]

एमआईपी

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

आईपीपी

आईपीपी (अनबाउंडेड आईपी) आईपी का एक वेरिएंट है जहां हम बीपीपी सत्यापनकर्ता को पीपी सत्यापनकर्ता द्वारा प्रतिस्थापित करते हैं। सामान्यतः हम इसको कॉम्प्लेटनेस और साउंडनेस की स्थितियों के निम्नानुसार संशोधित करते हैं:

  • कॉम्प्लेटनेस: यदि कोई स्ट्रिंग भाषा में है तो सत्यापनकर्ता को इस तथ्य के विषय में कम से कम 1/2 संभावना वाले एक ऑनेस्ट सूचक द्वारा कॉन्विंस्ड किया जाता है।
  • साउंडनेस: यदि स्ट्रिंग भाषा में नहीं है, तो 1/2 से कम संभावना को छोड़कर कोई भी प्रोवर ऑनेस्ट सत्यापनकर्ता को यह विश्वास नहीं दे सकता है कि यह भाषा में है।

हालाँकि आईपीपी भी PSPACE के बराबर है, आईपीपी प्रोटोकॉल ओरेकल के संबंध में आईपी से अपेक्षाकृत भिन्न है। सभी IPP=PSPACE ओरेकल के संबंध मेंIP ≠ PSPACE के लगभग सभी प्रोटोकॉल ओरेकल के संबंध में है।[4]

क्यूआईपी

क्वांटम इंटरएक्टिव प्रोटोकॉल आईपी का एक संस्करण है जो बीपीपी सत्यापनकर्ता को बीक्यूपी सत्यापनकर्ता द्वारा प्रतिस्थापित करता है, जहां बीक्यूपी पोलिनोमिअल टाइम में क्वांटम कंप्यूटर द्वारा हल की जाने वाली समस्याओं की क्लास है। संदेश क्वैबिट से बने होते हैं। 2009 में जैन जी उपाध्याय और वॉट्रस ने सिद्ध किया कि QIP भी PSPACE के बराबर है[5] जिसका अर्थ है कि यह परिवर्तन प्रोटोकॉल को कोई अतिरिक्त पावर नहीं देता है। यह किताएव और वॉट्रस के पिछले परिणाम को समाहित करता है कि क्यूआईपी ऍक्स्पटीआईएमई में समाहित है क्योंकि QIP = QIP होता है। इसलिए इसे तीन से अधिक राउंड कभी भी आवश्यक नहीं होते हैं।[6]

कॉम्पआईपी

सामान्यतः आईपीपी और क्यूआईपी सत्यापनकर्ता को अधिक पावर देते हैं। एक कॉम्पआईपी सिस्टम (प्रतिस्पर्धी आईपी प्रूफ सिस्टम) कॉम्प्लेटनेस की स्थिति को एक प्रकार से कमजोर (वीक) कर देता है जिससे प्रोवर वीक हो जाता है:

  • कॉम्प्लेटनेस: यदि कोई स्ट्रिंग भाषा एल में है, तो सत्यापनकर्ता को कम से कम 2/3 संभावना के साथ एक प्रोवर द्वारा इस तथ्य के विषय में कॉन्विंस्ड किया जाता है। इसके अतिरिक्त भाषा एल के लिए ओरेकल द्वारा एक्सेस दिए जाने पर प्रोवर प्रॉबबिलिस्टिक पोलिनोमिअल टाइम निम्नलिखित हो सकता है:

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

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

टिप्पणियाँ

  1. Chang Richard; et al. (1994). "यादृच्छिक दैवज्ञ परिकल्पना झूठी है". Journal of Computer and System Sciences. 49 (1): 24–39. doi:10.1016/s0022-0000(05)80084-4.
  2. Shamir, Adi. "Ip= pspace." Journal of the ACM 39.4 (1992): 869-877.
  3. Furer Martin, Goldreich Oded, Mansour Yishay, Sipser Michael, Zachos Stathis (1989). "इंटरएक्टिव प्रूफ सिस्टम में पूर्णता और सुदृढ़ता पर". Advances in Computing Research: A Research Annual. 5: 429–442. CiteSeerX 10.1.1.39.9412.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  4. R. Chang, B. Chor, Oded Goldreich, J. Hartmanis, J. Håstad, D. Ranjan, and P. Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39. 1994.
  5. Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (2009). "QIP = PSPACE". arXiv:0907.4737 [quant-ph].
  6. A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 608-617. 2000.
  7. Shafi Goldwasser and Mihir Bellare. The Complexity of Decision versus Search. SIAM Journal on Computing, Volume 23, No. 1. February 1994.
  8. Cai JY, Threlfall RA (2004). "द्विघात अवशिष्टता और यूपी पर एक नोट". Information Processing Letters. 92 (3): 127–131. CiteSeerX 10.1.1.409.1830. doi:10.1016/j.ipl.2004.06.015.


संदर्भ