View source for आईपी (कॉम्प्लेक्सिटी)

[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में क्लास '''आईपी''' (इंटरैक्टिव-प्रूफ) एक [[ इंटरैक्टिव प्रमाण प्रणाली |इंटरैक्टिव प्रूफ सिस्टम (आईपीएस)]] द्वारा हल की जाने वाली समस्याओं की क्लास है। यह क्लास पीएसपीएसीई के बराबर है। जिसके परिणाम को पेपर की एक सीरीज (श्रेणी) में स्थापित किया गया था। इसके प्रथम प्रकाशन को कार्लॉफ, फ़ोर्टनो और निसान द्वारा प्रदर्शित किया गया था जिसमे सीओ-एनपी के पास कई प्रोवर इंटरैक्टिव प्रमाण थे, और दूसरे प्रकाशन को शमीर द्वारा <code>IP = PSPACE</code> मे स्थापित करने के लिए कई तकनीकों को नियोजित किया गया था।<ref>{{cite journal | author = Chang Richard|display-authors=etal | year = 1994 | title = यादृच्छिक दैवज्ञ परिकल्पना झूठी है| journal = Journal of Computer and System Sciences | volume = 49 | issue = 1| pages = 24–39 | doi=10.1016/s0022-0000(05)80084-4| doi-access = free }}</ref><ref>Shamir, Adi. "Ip= pspace." Journal of the ACM 39.4 (1992): 869-877.</ref>

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

[[File:Interactive proof (complexity).svg|thumb|300px|एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।]]

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

:<math>w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accepts }w] \ge \tfrac{2}{3}</math>
:<math>w \not \in L \Rightarrow \Pr[V \leftrightarrow Q\text{ accepts }w] \le \tfrac{1}{3}</math>
लास्ज़लो बाबई द्वारा प्रस्तुत आर्थर-मर्लिन प्रोटोकॉल में समान होता है यदि इसके स्थानांतरण के समय की संख्या पोलिनोमिअल के अतिरिक्त एक स्थिरांक से संबद्ध होती है।

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

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

==आईपी = पीएसपीएसीई==
सामान्यतः प्रमाण को दो <code>IP ⊆ PSPACE</code> और <code>PSPACE ⊆ IP</code> भागों में विभाजित किया जा सकता है।

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

: <math>\Pr[V\text{ accepts }w\text{ starting at }M_j] = \max\nolimits_P \Pr \left [V \leftrightarrow P\text{ accepts }w\text{ starting at }M_j \right ] </math>
प्रत्येक 0 ≤ j ≤ p और प्रत्येक संदेश स्टोरेज ''M<sub>j</sub>'' के लिए हम फ़ंक्शन ''N<sub>Mj</sub>'' को प्रेरक रूप से परिभाषित करते हैं:

: <math>N_{M_j} =  \begin{cases}
  0 & j = p\text{ and }m_p = \text{reject}\\
  1 & j = p\text{ and }m_p = \text{accept}\\
  \max_{m_{j+1}} N_{M_{j+1}} & j < p\text{ and }j\text{ is odd} \\
  \text{wt-avg}_{m_{j+1}} N_{M_{j+1}} & j < p\text{ and }j\text{ is even} \\
\end{cases}</math>
जहाँ:

: <math>\text{wt-avg}_{m_{j+1}} N_{M_{j+1}} := \sum\nolimits_{m_{j+1}} \Pr\nolimits_r[V(w,r,M_j)=m_{j+1}]N_{M_{j+1}}</math>
जहां Pr<sub>''r''</sub> लंबाई p की यादृच्छिक स्ट्रिंग r पर ली गई प्रोबेबिलिटी है। सामान्यतः यह ''N<sub>Mj+1</sub>'' का औसत है जो इस प्रोबेबिलिटी (संभाव्यता) पर आधारित है कि सत्यापनकर्ता ने संदेश ''m<sub>j+1</sub>'' भेजा है। यदि M<sub>0</sub> को रिक्त संदेश अनुक्रम मानें तब हम प्रदर्शित कर सकते हैं कि ''N<sub>M0</sub>'' की गणना पोलिनोमिअल-स्पेस में की जा सकती है और ''N<sub>M0</sub>'' = Pr मे [V, w] को स्वीकृत किया जा सकता है। सबसे पहले ''N<sub>M0</sub>'' की गणना करने के लिए एक एल्गोरिदम प्रत्येक j और M<sub>j</sub> के लिए N<sub>Mj</sub> मानों की पुनरावर्ती करके गणना कर सकता है। चूँकि रिकर्शन p है जिसके लिए केवल पोलिनोमिअल क्लास आवश्यक होती है। दूसरी आवश्यकता यह है कि हमें ''N<sub>M0</sub>'' = Pr मे [V, w] की आवश्यकता होती है। जिससे यह निर्धारित किया जा सके कि आवश्यक मान w, A में सम्मिलित है या नहीं सम्मिलित है। इसे सिद्ध करने के लिए हम प्रूवर का उपयोग इस प्रकार करते हैं।

सामान्यतः हमें यह दिखाना होगा कि 0 ≤ j ≤ p प्रत्येक M<sub>j</sub> के लिए N''<sub>Mj</sub>'' = Pr, V, M<sub>j</sub> से प्रारंभ करके w को स्वीकृत करता है और हम j पर इंडक्शन का उपयोग कर सकते है। जहां j = p के लिए सिद्ध करना है। फिर हम p से 0 तक जाने के लिए इंडक्शन का उपयोग कर सकते हैं। ''j'' = ''p'' का आधार अपेक्षाकृत सरल होता है। चूंकि ''m<sub>p</sub>'' या तो एक्सेप्ट या रेजेक्ट है, यदि ''m<sub>p</sub>'' एक्सेप्ट है, तो ''N<sub>Mp</sub>'' को 1 के रूप में परिभाषित किया जा सकता है और यदि Pr[''V,'' ''M<sub>j</sub>''] = 1 है तब संदेश स्ट्रीम एक्सेप्ट (स्वीकृत) को इंगित करता है। इस प्रकार सिद्ध है कि ''m<sub>p</sub>'' अस्वीकृत है। इंडुक्टिव परिकल्पना के लिए हम मानते हैं कि कुछ j+1 ≤ p और किसी भी संदेश अनुक्रम M<sub>j+1</sub> के लिए ''M<sub>j+1</sub>'', ''N<sub>Mj+1</sub>'' = <math>Pr \left [V\text{ accepts }w\text{ starting at }M_{j+1} \right ]</math>, j और किसी भी संदेश अनुक्रम M<sub>j</sub> के लिए परिकल्पना को सिद्ध किया जा सकता है।

''N<sub>Mj</sub>'' की परिभाषा के अनुसार यदि j सम है तो ''m<sub>j+1,</sub>'' V से P तक एक संदेश है:

:<math>N_{M_j} = \sum\nolimits_{m_{j+1}} \Pr\nolimits_r \left [V(w,r,M_j)=m_{j+1} \right ] N_{M_{j+1}}.</math>
तब इंडुक्टिव परिकल्पना द्वारा हम कह सकते हैं कि यह बराबर है: 

:<math>\sum\nolimits_{m_{j+1}} \Pr\nolimits_r \left [V(w,r,M_j)=m_{j+1} \right ] * \Pr \left [V\text{ accepts }w\text{ starting at }M_{j+1} \right ].</math>
अंत में, परिभाषा के अनुसार हम देख सकते हैं कि यह <math>Pr \left [V\text{ accepts }w\text{ starting at }M_{j+1} \right ]</math> के बराबर है।

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

:<math>N_{M_j} = \max\nolimits_{m_{j+1}} N_{M_{j+1}}.</math>
तब इंडुक्टिव परिकल्पना द्वारा यह बराबर होता है:

:<math>\max\nolimits_{m_{j+1}} * \Pr[V\text{ accepts }w\text{ starting at }M_{j+1}].</math>
यह <math>Pr \left [V\text{ accepts }w\text{ starting at }M_{j+1} \right ]</math> के बराबर है:

: <math>\max\nolimits_{m_{j+1}} \Pr[V\text{ accepts }w\text{ starting at }M_{j+1}] \leq \Pr[V\text{ accepts w starting at }M_j]</math>
क्योंकि दाहिनी ओर का सूचक बायीं ओर की अभिव्यक्ति को अधिकतम करने के लिए संदेश m<sub>j+1</sub> भेज सकता है:

: <math>\max\nolimits_{m_{j+1}} \Pr\left[V\text{ accepts }w\text{ starting at }M_{j+1} \right] \geq \Pr\left[V\text{ accepts }w\text{ starting at }M_j\right]</math>
चूँकि प्रोवर उसी संदेश को भेजने के अतिरिक्त कुछ नहीं कर सकता है। इस प्रकार यह मानता है कि क्या i सम है या विषम है सामान्यतः इसका प्रमाण है कि <code>IP ⊆ PSPACE</code> पूर्ण है।

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

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

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

: <math>\#\text{SAT} = \left \{ \langle \varphi, k \rangle \ : \  \varphi \text{ is a CNF-formula with exactly } k \text{ satisfying assignments} \right \}.</math>
ध्यान दें कि यह एसएटी की सामान्य परिभाषा से अलग है, क्योंकि यह एक फ़ंक्शन के अतिरिक्त एक निर्णय समस्या है।

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

{| border="1" cellpadding="2"
|''a'' ∧ ''b'' ||  ''ab''
|-
|''a'' ∨ ''b'' || ''a'' ∗ ''b'' := 1 − (1 − ''a'')(1 − ''b'') 
|-
| ¬''a'' || 1 − ''a''
|+ बूलियन सूत्र φ(b<sub>1</sub>, ..., b<sub>n</sub>) को पोलिनोमिअल pφ(x<sub>1</sub>, ..., x<sub>n</sub>) में परिवर्तित करने के लिए अंकगणितीय नियम
|}
उदाहरण के लिए φ = a ∧ (b ∨ ¬c) को निम्नानुसार पोलिनोमिअल में परिवर्तित किया जा सकता है:

:<math>\begin{align} 
p_\varphi &= a \wedge (b \vee \neg c) \\
&= a \wedge \left (b * (1-c) \right ) \\
&= a \wedge \left ( 1 - (1-b)(1 - (1-c)) \right ) \\
&= a \left ( 1 - (1-b)(1 - (1-c)) \right ) \\
&= a - (ac-abc) 
\end{align}</math>
ऑपरेटर ab और a ∗ b में से प्रत्येक का परिणाम एक पोलिनोमिअल में होता है, जिसकी डिग्री a और b के लिए पोलिनोमिअल की डिग्री के योग के बराबर होती है। इसलिए किसी भी वेरिएबल की डिग्री अधिकतम φ की लंबाई होती है।

माना कि F एक परिमित क्षेत्र है जिसका अनुक्रम q > 2n है, साथ ही माना कि q का मान कम से कम 1000 है और प्रत्येक 0 ≤ i ≤ n के लिए F पर <math>a_1, \dots, a_{i-1}\in F</math> पैरामीटर वाले एक फ़ंक्शन φ को परिभाषित किया जाता है और 0 ≤ i के लिए F में एक एकल वेरिएबल a<sub>i</sub> है जहां n और <math>a_1, \dots, a_i \in F</math> हैं:
:<math>f_i(a_1, \dots, a_i) = \sum\nolimits_{a_{i+1}, \dots, a_n \in \{0, 1\}} p(a_1, \dots, a_n).</math>
:ध्यान दें कि f<sub>0</sub> का मान φ के संतोषजनक असाइनमेंट की संख्या है। f<sub>0</sub> एक शून्य फ़ंक्शन है, जिसमें कोई वेरिएबल नहीं है।

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

* '''फेज 0:''' प्रूवर P एक अभाज्य संख्या q > 2n चुनता है और f<sub>0</sub> की गणना करता है, फिर यह सत्यापनकर्ता V को q और f<sub>0</sub> भेजता है। जहां V जाँच करता है कि q अधिकतम (1000, 2n) से बड़ा अभाज्य है और f<sub>0</sub>() = k है।
* '''फेज 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> भेजता है।
* '''फेज n+1:''' V मूल्यांकन करता है कि <math>p(r_1, \dots, r_n)</math> की तुलना करने के लिए <math>f_n(r_1, \dots, r_n)</math> यदि समान हैं तो V स्वीकृत है, अथवा V अस्वीकृत है।

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

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

फेज 0 में V को अस्वीकृत करने से रोकने के लिए <math>\tilde P</math> को एक गलत मान <math>\tilde f_0()</math> भेजना होगा। फिर, फेज 1 में <math>\tilde P</math> को <math>\tilde f_1(0)+\tilde f_1(1) = \tilde f_0()</math> मान के साथ एक गलत पोलिनोमिअल <math>\tilde f_1</math> भेजना होगा। तब V, P को भेजने के लिए एक यादृच्छिक मान r<sub>1</sub> चुनता है:
:<math>\Pr \left [\tilde f_1(r_1) = f_1(r_1) \right ] < \tfrac{1}{n^2}.</math> 
:इसका कारण यह है कि डिग्री के एकल वेरिएबल वाले पोलिनोमिअल में अधिकतम d के मूल d से अधिक नहीं हो सकते हैं। जब तक कि इसका मूल्यांकन 0 न हो। अतः डिग्री के एक ही वेरिएबल में अधिकतम d वाले कोई भी दो पोलिनोमिअल केवल d स्थानों पर ही समान हो सकते हैं। चूंकि |''F''| > 2<sup>''n''</sup> r<sub>1</sub> के इन मानों में से एक होने की संभावना अधिकतम <math>n/2^n < n/n^3</math> है यदि n > 10 या अधिकतम (n/1000) ≤ (n/n3) यदि n ≤ 10 है।

इस विचार को अन्य फेजों के लिए सामान्यीकृत करना हमारे पास प्रत्येक: मान 1 ≤ i ≤ n के लिए है:
:<math>\tilde f_{i-1}(r_1, \dots, r_{i-1}) \neq f_{i-1}(r_1, \dots, r_{i-1}),</math> 
:फिर F से यादृच्छिक रूप से चुने गए r<sub>i</sub> के लिए,
:<math>\Pr \left [\tilde f(r_1, \dots, r_i) = f_i(r_1, \dots, r_i) \right ] \leq \tfrac{1}{n^2}.</math>
:वहाँ n फेज हैं, इसलिए संभावना है कि <math>\tilde P</math> सत्य है क्योंकि V किसी फेज में एक सुविधाजनक r<sub>i</sub> का चयन करता है जो अधिकतम 1/n है। इसलिए कोई भी सूचक सत्यापनकर्ता को 1/n से अधिक संभावना के साथ स्वीकृत करने के लिए बाध्य नहीं कर सकता है। हम परिभाषा से यह भी देख सकते हैं कि सत्यापनकर्ता V संभाव्य पोलिनोमिअल समय में कार्य करता है। इस प्रकार <code>SAT ∈ IP</code> है।

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

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

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

: <math>\psi = \mathsf Q_1 x_1 \dots \mathsf Q_mx_m[\varphi]</math>
जहां φ एक सीएनएफ सूत्र है। तब क्यूई एक परिमाणक है या तो ∃ या ∀ अब φ पिछले प्रमाण के समान ही है, लेकिन अब इसमें क्वांटिफायर भी सम्मिलित है:

: <math>f_i(a_1, \dots, a_i) =  \begin{cases}
f_i(a_1, \dots, a_m) =  1 & \mathsf Q_{i+1}x_{i+1}\dots \mathsf Q_mx_m[\varphi(a_1, \dots, a_i)] \text{ is true}\\
0 & \text{otherwise}
\end{cases} </math>
यहां φ(a<sub>1</sub>, ..., a<sub>i</sub>) φ है जिसमें x<sub>1</sub> से x<sub>i</sub> के स्थान पर a<sub>1</sub> से a<sub>i</sub> प्रतिस्थापित किया गया है। इस प्रकार f<sub>0</sub> ψ का सत्य मान है। ψ का अंकगणितीय मान निकालने के लिए हमें निम्नलिखित नियमों का उपयोग करना चाहिए:

:<math> f_i(a_1, \dots,a_i) = \begin{cases} f_{i+1}(a_1, \dots,a_i,0)\cdot f_{i+1}(a_1, \dots,a_i,1) & \mathsf Q_{i+1} = \forall \\
f_{i+1}(a_1, \dots,a_i,0) * f_{i+1}(a_1, \dots,a_i,1) & \mathsf Q_{i+1} = \exists
\end{cases}</math>
जबकि पहले हम x * y = 1 − (1 − x)(1 − y) परिभाषित करते थे।

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

तो अब इससे पहले कि हम <math>\psi = \mathsf Q_1x_1\dots \mathsf Q_mx_m[\varphi]</math> की एक नई अभिव्यक्ति प्रस्तुत करते हैं:

: <math>\psi' = \mathsf Q_1 \mathrm R x_1 \mathsf Q_2 \mathrm R x_1 \mathrm R x_2\dots \mathsf Q_m \mathrm R x_1 \dots \mathrm R x_m [\varphi]</math>
या दूसरे प्रकार से,

: <math>\psi' = \mathsf S_1 y_1\dots \mathsf S_k y_k[\varphi], \qquad \text{ where }\mathsf S_i \in \{ \forall ,\exists , \mathrm R\}, \ y_i \in \{ x_1,\dots,x_m\}</math>
अब प्रत्येक i ≤ k के लिए हम फ़ंक्शन f<sub>i</sub> को परिभाषित करते हैं। और <math>f_k(x_1,\dots,x_m)</math> को पोलिनोमिअल p(x<sub>1</sub>, ..., x<sub>m</sub>) के रूप में भी परिभाषित करते हैं जिससे φ को अंकगणितीय रूप मे प्राप्त किया जाता है। फिर पोलिनोमिअल की डिग्री को अपेक्षाकृत कम रखने के लिए हम f<sub>i</sub> को f<sub>i+1</sub> के रूप में परिभाषित करते हैं:

:<math>\text{If }\mathsf S_{i+1} = \forall, \quad f_i(a_1,\dots,a_i) = f_{i+1}(a_1,\dots,a_i,0) \cdot f_{i+1}(a_1,\dots,a_i,1) </math>
:<math>\text{If }\mathsf S_{i+1} = \exists, \quad f_i(a_1,\dots,a_i) = f_{i+1}(a_1,\dots,a_i,0) * f_{i+1}(a_1,\dots,a_i,1) </math>
:<math>\text{If }\mathsf S_{i+1} = \mathrm R, \quad f_i(a_1,\dots,a_i,a) =  (1-a)f_{i+1}(a_1,\dots,a_i,0) + a f_{i+1}(a_1,\dots,a_i,1)</math>
अ'''ब हम देख सकते हैं कि कमी संक्रिया R, बहुपद की डिग्री को नहीं बदलती है। यह भी देखना महत्वपूर्ण है कि आरएक्स ऑपरेशन बूलियन इनपुट पर फ़ंक्शन के मान को नहीं बदलता है। तो f0 अभी भी ψ का सत्य मान है, लेकिन R<sub>x</sub> मान एक परिणाम उत्पन्न करता''' है जो x में रैखिक है। इसके अतिरिक्त किसी भी <math>\mathsf Q_i x_i</math> के बाद हम <math>\mathrm R_{x_1}\dots \mathrm R_{x_i}</math>को जोड़ते हैं। <math>\mathsf Q_i</math> को ψ′ में अंकगणित करने के बाद डिग्री को 1 तक कम करने के लिए।

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

* '''फेज़ 0:''' P → V: P, V को f0 भेजता है। V जाँच करता है कि f0= 1 है और यदि नहीं है तो अस्वीकार कर देता है।
* '''फेज़ 1:''' P → V: P, V को ''f''<sub>1</sub>(''z'') भेजता है। V, ''f''<sub>1</sub>(0) और ''f''<sub>1</sub>(1) का मूल्यांकन करने के लिए गुणांक का उपयोग करता है। फिर यह जाँचता है कि बहुपद की डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:
::<math>f_{0}(\varnothing) = \begin{cases}
f_{1}(0)\cdot f_{1}(1) & \text{ if }\mathsf S = \forall \\
f_{1}(0) * f_{1}(1) & \text{ if }\mathsf S = \exists. \\
(1-r)f_{1}(0) + rf_{1}(1) & \text{ if }\mathsf S = \mathrm R.
\end{cases}</math>
:यदि दोनों में से कोई भी विफल रहता है तो अस्वीकृत करें।

* चरण i: P → V: P, z में बहुपद के रूप में <math>f_i(r_1,\dots,r_{i-1},z)</math> भेजता है। <math>r_1,\dots,r_{i-1}</math> के लिए पहले से निर्धारित यादृच्छिक मानों को दर्शाता है
V मूल्यांकन के लिए गुणांकों का उपयोग करता है <math>f_i(r_1,\dots,r_{i-1},0)</math> और <math>f_i(r_1,\dots,r_{i-1},1)</math>. फिर यह जाँचता है कि पोलिनोमिअल डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:
:<math>f_{i-1}(r_1,\dots,r_{i-1}) = \begin{cases} f_{i}(r_1,\dots,r_{i-1},0)\cdot f_{i}(r_1,\dots, r_{i-1},1) & \mathsf S = \forall \\
f_{i}(r_1,\dots,r_{i-1},0) * f_i(r_1, \dots,r_{i-1},1) & \mathsf S = \exists.
\end{cases}</math>
:<math>f_{i-1}(r_1\dots r) = (1-r)f_{i}(r_1,\dots,r_{i-1},0) + rf_{i}(r_1,\dots,r_{i-1},1)\text{ if }\mathsf S = \mathrm R.</math>
यदि दोनों में से कोई भी विफल रहता है तो अस्वीकृत कर दें।

वी → पी: वी एफ में एक यादृच्छिक आर चुनता है और इसे पी को भेजता है। (यदि <math>\mathsf S=\mathrm R</math> तब यह r पिछले r को प्रतिस्थापित कर देता है)।

फेज i +1 पर जाएं जहां P को V को इस बात के लिए राजी करना होगा <math>f_i(r_1,\dots,r)</math> सही है।

* फेज ''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 पर अस्वीकृत कर देगा।

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

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

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

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

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

:<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>
===एमआईपी===
{{main|इंटरएक्टिव प्रूफ सिस्टम#एमआईपी
}}

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

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

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

हालाँकि आईपीपी भी <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|क्वांटम इंटरएक्टिव प्रोटोकॉल
}}

[[क्वांटम इंटरएक्टिव प्रोटोकॉल]] आईपी का एक संस्करण है जो बीपीपी सत्यापनकर्ता को [[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>
===कॉम्पआईपी ===
सामान्यतः आईपीपी और क्यूआईपी सत्यापनकर्ता को अधिक पावर देते हैं। एक कॉम्पआईपी सिस्टम (प्रतिस्पर्धी आईपी प्रूफ सिस्टम) कॉम्प्लेटनेस की स्थिति को एक प्रकार से कमजोर (वीक) कर देता है जिससे प्रोवर वीक हो जाता है:

* '''कॉम्प्लेटनेस:''' यदि कोई स्ट्रिंग भाषा एल में है, तो सत्यापनकर्ता को कम से कम 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>
== टिप्पणियाँ ==
<!--See http://en.wikipedia.org/wiki/Wikipedia:Footnotes for an explanation of how to generate footnotes using the <ref(erences/)> tags-->
<references/>


== संदर्भ ==
* Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp.&nbsp;421&ndash;429.
* [[Shafi Goldwasser]], [[Silvio Micali]], and [[Charles Rackoff]]. [http://portal.acm.org/citation.cfm?id=63434 The Knowledge complexity of interactive proof-systems]. ''Proceedings of 17th ACM Symposium on the Theory of Computation'', Providence, Rhode Island. 1985, pp.&nbsp;291&ndash;304. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract]
* 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 the 18th Annual ACM Symposium on Theory of Computation''. ACM, New York, 1986, pp.&nbsp;59&ndash;68.
* Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [https://arxiv.org/abs/0907.4737]
* [[Carsten Lund|Lund, C.]], [[Lance Fortnow|Fortnow, L.]], Karloff, H., [[Noam Nisan|Nisan, N.]] Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp.&nbsp;2&ndash;90.
* Adi Shamir. [http://portal.acm.org/citation.cfm?doid=146585.146609 IP = PSPACE]. ''Journal of the ACM'', volume 39, issue 4, p.&nbsp;869&ndash;877. October 1992.
* Alexander Shen. [http://doi.acm.org/10.1145/146585.146613 IP=PSpace: Simplified Proof]. J.ACM, v. 39(4), pp.&nbsp;878&ndash;880, 1992.
* {{CZoo|IP|I#ip}}, [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#mip MIP], [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ipp IPP], [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip QIP], [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2 QIP(2)], [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#compip compIP], [http://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#frip frIP]

{{ComplexityClasses}}
[[Category: संभाव्य जटिलता वर्ग]] [[Category: प्रमाण युक्त लेख]] 



[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]