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

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

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

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

परिभाषा

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

$w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]\geq {\tfrac {2}{3}}$

$w\not \in L\Rightarrow \Pr[V\leftrightarrow Q{\text{ accepts }}w]\leq {\tfrac {1}{3}}$

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

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

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

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

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

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

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

$\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]$

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

$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}}$

जहाँ:

${\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}}$

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

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

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

$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}}.$

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

$\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].$

अंत में, परिभाषा के अनुसार हम देख सकते हैं कि यह $Pr\left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right]$ के बराबर है।

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

$N_{M_{j}}=\max \nolimits _{m_{j+1}}N_{M_{j+1}}.$

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

$\max \nolimits _{m_{j+1}}*\Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}].$

यह $Pr\left[V{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right]$ के बराबर है:

$\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}]$

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

$\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]$

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

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

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

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

एसएटी आईपी

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

$\#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{ is a CNF-formula with exactly }}k{\text{ satisfying assignments}}\right\}.$

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

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

बूलियन सूत्र φ(b₁, ..., b_n) को पोलिनोमिअल pφ(x₁, ..., x_n) में परिवर्तित करने के लिए अंकगणितीय नियम

a ∧ b	ab
a ∨ b	a ∗ b := 1 − (1 − a)(1 − b)
¬a	1 − a

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

${\begin{aligned}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{aligned}}$

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

अब मान लीजिए कि F एक परिमित क्षेत्र है जिसका क्रम q > 2n है, साथ ही यह भी माने कि q कम से कम 1000 है और प्रत्येक 0 ≤ i ≤ n के लिए F पर $a_{1},\dots ,a_{i-1}\in F$ पैरामीटर वाले एक फ़ंक्शन φ को परिभाषित करें, और 0 ≤ i के लिए F में एक एकल वेरिएबल a_i परिभाषित करें। ≤ n और $a_{1},\dots ,a_{i}\in F$ के लिए चलो

$f_{i}(a_{1},\dots ,a_{i})=\sum \nolimits _{a_{i+1},\dots ,a_{n}\in \{0,1\}}p(a_{1},\dots ,a_{n}).$

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

अब #SAT का प्रोटोकॉल इस प्रकार काम करता है:

• वेरिएबलण 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 भेजता है।
• P, z में पोलिनोमिअल के रूप में $f_{i}(r_{1},\dots ,r_{i-1},z)$ के गुणांक भेजता है। V सत्यापित करता है कि fi की डिग्री n से कम है और वह $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)$ (यदि नहीं तो V अस्वीकृत करता है)। V अब F से P को एक यादृच्छिक संख्या ri भेजता है।
• 'वेरिएबलण n+1': V मूल्यांकन करता है $p(r_{1},\dots ,r_{n})$ मूल्य से तुलना करने के लिए $f_{n}(r_{1},\dots ,r_{n})$. यदि वे समान हैं तो V स्वीकृत करता है, अन्यथा V अस्वीकृत करता है।

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

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

वेरिएबलण 0 में वी को अस्वीकृत करने से रोकने के लिए, ${\tilde {P}}$ को पी को एक गलत मान ${\tilde {f}}_{0}()$ भेजना होगा। फिर, वेरिएबलण 1 में, ${\tilde {P}}$ को ${\tilde {f}}_{1}(0)+{\tilde {f}}_{1}(1)={\tilde {f}}_{0}()$ की संपत्ति के साथ एक गलत पोलिनोमिअल ${\tilde {f}}_{1}$ भेजना होगा। जब V, P को भेजने के लिए एक यादृच्छिक r1 चुनता है,

$\Pr \left[{\tilde {f}}_{1}(r_{1})=f_{1}(r_{1})\right]<{\tfrac {1}{n^{2}}}.$

इसका कारण यह है कि घात के एकल वेरिएबल वाले पोलिनोमिअल में अधिकतम d के मूल d से अधिक नहीं हो सकते हैं (जब तक कि इसका मूल्यांकन हमेशा 0 न हो)। अतः, घात के एक ही वेरिएबल में अधिकतम d वाले कोई भी दो पोलिनोमिअल केवल d स्थानों पर ही समान हो सकते हैं। चूंकि |एफ| > 2n r1 के इन मानों में से एक होने की संभावना अधिकतम $n/2^{n}<n/n^{3}$ है यदि n > 10, या अधिकतम (n/1000) ≤ (n/n3) यदि n ≤ 10 है।

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

${\tilde {f}}_{i-1}(r_{1},\dots ,r_{i-1})\neq f_{i-1}(r_{1},\dots ,r_{i-1}),$ फिर आर के लिए_iF से यादृच्छिक रूप से चुना गया,

$\Pr \left[{\tilde {f}}(r_{1},\dots ,r_{i})=f_{i}(r_{1},\dots ,r_{i})\right]\leq {\tfrac {1}{n^{2}}}.$

वहाँ n वेरिएबलण हैं, इसलिए संभावना है कि ${\tilde {P}}$ भाग्यशाली है क्योंकि V किसी वेरिएबलण में एक सुविधाजनक ri का चयन करता है जो अधिकतम 1/n है। इसलिए, कोई भी सूचक सत्यापनकर्ता को 1/n से अधिक संभावना के साथ स्वीकृत करने के लिए बाध्य नहीं कर सकता है। हम परिभाषा से यह भी देख सकते हैं कि सत्यापनकर्ता V संभाव्य पोलिनोमिअल समय में काम करता है। इस प्रकार, #SAT ∈ IP.

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

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

हम जानते हैं कि TQBF PSPACE-Complete में है। तो मान लीजिए कि ψ एक परिमाणित बूलियन अभिव्यक्ति है:

$\psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]$

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

$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}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i})]{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}$

यहाँ, φ(ए₁, ..., ए_i) ए के साथ φ है₁ एक को_ix के स्थान पर प्रतिस्थापित₁ एक्स को_i. इस प्रकार एफ₀ ψ का सत्य मान है। ψ का अंकगणित करने के लिए हमें निम्नलिखित नियमों का उपयोग करना चाहिए:

$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}}$

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

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

तो अब इससे पहले कि हम अंकगणित करें $\psi ={\mathsf {Q}}_{1}x_{1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi ]$ हम एक नई अभिव्यक्ति प्रस्तुत करते हैं:

$\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 ]$

या दूसरे तरीके से कहें:

$\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}\}$

अब प्रत्येक i ≤ k के लिए हम फ़ंक्शन f को परिभाषित करते हैं_i. हम भी परिभाषित करते हैं $f_{k}(x_{1},\dots ,x_{m})$ पोलिनोमिअल p(x) होना₁, ..., एक्स_m) जो φ का अंकगणित करके प्राप्त किया जाता है। अब पोलिनोमिअल की घात को कम रखने के लिए, हम f को परिभाषित करते हैं_iएफ के संदर्भ में_i+1:

${\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)$

${\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)$

${\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)+af_{i+1}(a_{1},\dots ,a_{i},1)$

अब हम देख सकते हैं कि कमी संक्रिया R, पोलिनोमिअल की डिग्री को नहीं बदलती है। यह भी देखना जरूरी है कि आर_xऑपरेशन बूलियन इनपुट पर फ़ंक्शन का मान नहीं बदलता है। तो एफ₀ अभी भी ψ का सत्य मान है, लेकिन R_xमान एक ऐसा परिणाम उत्पन्न करता है जो x में रैखिक होता है। किसी के बाद भी ${\mathsf {Q}}_{i}x_{i}$ हम जोड़ते हैं $\mathrm {R} _{x_{1}}\dots \mathrm {R} _{x_{i}}$ अंकगणित के बाद डिग्री को 1 तक कम करने के लिए ψ′ में ${\mathsf {Q}}_{i}$.

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

• 'वेरिएबलण 0': पी → वी: पी एफ भेजता है₀ से वी. वी. जाँचता है कि एफ₀= 1 और यदि नहीं तो अस्वीकृत कर देता है।
• वेरिएबलण 1: पी → वी: पी एफ भेजता है₁(z) से V. V, f का मूल्यांकन करने के लिए गुणांक का उपयोग करता है₁(0) और एफ₁(1). फिर यह जाँचता है कि पोलिनोमिअल डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:

$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}}$

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

• वेरिएबलण I: पी → वी: पी भेजता है $f_{i}(r_{1},\dots ,r_{i-1},z)$ z में एक पोलिनोमिअल के रूप में। आर₁ के लिए पहले से निर्धारित यादृच्छिक मानों को दर्शाता है $r_{1},\dots ,r_{i-1}$

V मूल्यांकन के लिए गुणांकों का उपयोग करता है $f_{i}(r_{1},\dots ,r_{i-1},0)$ और $f_{i}(r_{1},\dots ,r_{i-1},1)$. फिर यह जाँचता है कि पोलिनोमिअल डिग्री अधिकतम n है और निम्नलिखित सर्वसमिकाएँ सत्य हैं:

$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}}$

$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} .$

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

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

वेरिएबलण i +1 पर जाएं जहां P को V को इस बात के लिए राजी करना होगा $f_{i}(r_{1},\dots ,r)$ सही है।

• वेरिएबलण k + 1: V, $p(r_{1},\dots ,r_{m})$ का मूल्यांकन करता है। फिर यह जांचता है कि क्या $p(r_{1},\dots ,r_{m})=f_{k}(r_{1},\dots ,r_{m})$ यदि वे बराबर हैं तो V स्वीकृत करता है, अन्यथा V अस्वीकृत कर देता है। यह प्रोटोकॉल विवरण का अंत है.

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

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

वेरिएंट

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

डीआईपी

Main article: इंटरैक्टिव प्रूफ सिस्टम

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

उत्तम पूर्णता

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

$w\in L\Rightarrow \Pr[V\leftrightarrow P{\text{ accepts }}w]=1$

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

एमआईपी

Main article: इंटरएक्टिव प्रूफ सिस्टम § एमआईपी

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

आईपीपी

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

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

हालाँकि IPP भी PSPACE के बराबर है, IPP प्रोटोकॉल, Oracles के संबंध में IP से काफी भिन्न व्यवहार करता है IPP=PSPACE सभी Oracles के संबंध में, जबकिIP ≠ PSPACE लगभग सभी Oracles के संबंध में।

क्यूआईपी

Main article: क्वांटम इंटरएक्टिव प्रोटोकॉल

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

compIP

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

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

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

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

संदर्भ

• Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421–429.
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985, pp. 291–304. Extended abstract
• Shafi Goldwasser and Michael Sipser. 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. 59–68.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
• Lund, C., Fortnow, L., Karloff, H., Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on the Foundations of Computer Science. IEEE, New York, 1990, pp. 2–90.
• Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p. 869–877. October 1992.
• Alexander Shen. IP=PSpace: Simplified Proof. J.ACM, v. 39(4), pp. 878–880, 1992.
• Complexity Zoo: IP, MIP, IPP, QIP, QIP(2), compIP, frIP