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

From Vigyanwiki
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में क्लास '''आईपी''' (इंटरैक्टिव-प्रूफ) एक [[ इंटरैक्टिव प्रमाण प्रणाली |इंटरैक्टिव प्रूफ सिस्टम (आईपीएस)]] द्वारा हल की जाने वाली समस्याओं का वर्ग है। यह क्लास पीएसपीएसीई के बराबर है। परिणाम को कागजात की एक श्रृंखला में स्थापित किया गया था: लुंड, कार्लॉफ़, फ़ोर्टनो और निसान द्वारा पहला दिखाया गया कि सह-एनपी के पास कई प्रोवेर इंटरैक्टिव सबूत थे<ref>{{Cite book|last1=Lund|first1=C.|last2=Fortnow|first2=L.|last3=Karloff|first3=H.|last4=Nisan|first4=N.|title=Proceedings &#91;1990&#93; 31st Annual Symposium on Foundations of Computer Science |chapter=Algebraic methods for interactive proof systems |pages=2–10|publisher=IEEE Comput. Soc. Press|doi=10.1109/fscs.1990.89518|isbn=0-8186-2082-X|year=1990|s2cid=32614901}}</ref> और दूसरा, शमीर द्वारा, उस आईपी को स्थापित करने के लिए अपनी तकनीक को नियोजित किया गया = पीएसपीएसीई<ref>Shamir, Adi. "Ip= pspace." Journal of the ACM 39.4 (1992): 869-877.</ref> परिणाम एक प्रसिद्ध उदाहरण है जहां प्रमाण सापेक्ष नहीं होता है।<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>
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में क्लास '''आईपी''' (इंटरैक्टिव-प्रूफ) एक [[ इंटरैक्टिव प्रमाण प्रणाली |इंटरैक्टिव प्रूफ सिस्टम (आईपीएस)]] द्वारा हल की जाने वाली समस्याओं की क्लास है। यह क्लास पीएसपीएसीई के बराबर है। जिसके परिणाम को पेपर की एक सीरीज (श्रेणी) में स्थापित किया गया था। इसके प्रथम प्रकाशन को कार्लॉफ, फ़ोर्टनो और निसान द्वारा प्रदर्शित किया गया था जिसमे सीओ-एनपी के पास कई प्रोवर इंटरैक्टिव प्रमाण थे, और दूसरे प्रकाशन को शमीर द्वारा <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) का आदान-प्रदान करती हैं और एक बार बातचीत पूरी हो जाने पर, सत्यापनकर्ता को यह तय करना होगा कि एन भाषा में है या नहीं, त्रुटि की केवल 1/3 संभावना है। (इसलिए बीपीपी में कोई भी भाषा आईपी में है, तब से सत्यापनकर्ता केवल नीतिवचन को अनदेखा कर सकता है और स्वयं निर्णय ले सकता है।
इंटरैक्टिव प्रूफ सिस्टम की अवधारणा पहली बार 1985 में [[शफ़ी गोल्डवेसर]], [[सिल्वियो मिकाली]] और [[ चार्ल्स रैकॉफ़ |चार्ल्स रैकॉफ़]] द्वारा प्रस्तुत की गई थी। इंटरैक्टिव प्रूफ सिस्टम में दो प्रोवर और P मशीनें होती हैं जो एक प्रमाण को प्रस्तुत करती है कि एक दी गई [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]] n इसकी क्लास है तथा भाषा और सत्यापनकर्ता (वेरीफायर) V का परीक्षण करती है कि प्रस्तुत प्रमाण सही है। प्रोवर को गणना और स्टोरेज (भंडारण) में अनंत माना जाता है, जबकि सत्यापनकर्ता एक यादृच्छिक बिट स्ट्रिंग के साथ एक प्रॉबबिलिस्टिक पोलिनोमिअल टाइम मशीन है जिसकी लंबाई n के आकार पर पोलिनोमिअल होती है। ये दोनों मशीनें संदेशों की एक पोलिनोमिअल संख्या p(n) का स्थानांतरण करती हैं और एक बार स्थानांतरण पूर्ण हो जाने पर सत्यापनकर्ता को यह तय करना होता है कि n भाषा में है या n भाषा में नही है जिसमे त्रुटि की केवल 1/3 की संभावना होती है। इसीलिए बीपीपी में कोई भी भाषा आईपी के रूप मे हो सकती है। जिसमे सत्यापनकर्ता केवल प्रोवर को स्थानांतरित करके स्वयं निर्णय ले सकता है।


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


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


:<math>w \in L \Rightarrow \Pr[V \leftrightarrow P\text{ accepts }w] \ge \tfrac{2}{3}</math>
:<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>
:<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>IP ⊆ PSPACE</code> और PSPACE ⊆ IP
सामान्यतः प्रमाण (प्रूफ) को दो <code>IP ⊆ PSPACE</code> और <code>PSPACE ⊆ IP</code> भागों में विभाजित किया जा सकता है।


=== IP PSPACE===
=== आईपी पीएसपीएसीई===
उस <code>IP ⊆ PSPACE</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>
: <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>'' को प्रेरक रूप से परिभाषित करते हैं:
प्रत्येक 0 ≤ j ≤ p और प्रत्येक संदेश स्टोरेज ''M<sub>j</sub>'' के लिए हम फ़ंक्शन ''N<sub>Mj</sub>'' को प्रेरक रूप से परिभाषित करते हैं:


: <math>N_{M_j} =  \begin{cases}
: <math>N_{M_j} =  \begin{cases}
Line 34: Line 34:


: <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>
: <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>
जहां Prr लंबाई p की यादृच्छिक स्ट्रिंग r पर ली गई संभावना है। यह अभिव्यक्ति ''N<sub>Mj+1</sub>'' का औसत है, जो इस संभावना पर आधारित है कि सत्यापनकर्ता ने संदेश ''m<sub>j+1</sub>'' भेजा है।
जहां 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 में सम्मिलित है या नहीं सम्मिलित है। इसे सिद्ध करने के लिए हम प्रोवर का उपयोग इस प्रकार करते हैं।


M0 को खाली संदेश अनुक्रम मानें, यहां हम दिखाएंगे कि NM0 की गणना बहुपद स्थान में की जा सकती है, और NM0 = Pr[V, w को स्वीकार करता है]। सबसे पहले, NM0 की गणना करने के लिए, एक एल्गोरिदम प्रत्येक j और Mj के लिए NMj मानों की पुनरावर्ती गणना कर सकता है। चूँकि पुनरावृत्ति की गहराई p है, केवल बहुपद स्थान आवश्यक है। दूसरी आवश्यकता यह है कि हमें NM0 = 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> के लिए हाइपोथिसिस को सिद्ध किया जा सकता है।


हमें यह दिखाना होगा कि प्रत्येक 0 ≤ j ≤ p और प्रत्येक Mj के लिए, NMj = Pr[V Mj से प्रारंभ करके w को स्वीकार करता है], और हम j पर इंडक्शन का उपयोग करके ऐसा करेंगे। आधार मामला j = p के लिए सिद्ध करना है। फिर हम p से 0 तक जाने के लिए इंडक्शन का उपयोग करेंगे।
''N<sub>Mj</sub>'' की परिभाषा के अनुसार यदि j सम है तो ''m<sub>j+1,</sub>'' V से P तक एक संदेश है:
 
जे = पी का आधार मामला काफी सरल है। चूंकि एमपी या तो स्वीकार या अस्वीकार है, यदि एमपी स्वीकार है, तो एनएमपी को 1 के रूप में परिभाषित किया गया है और पीआर [वी एमजे से शुरू होने वाले डब्ल्यू को स्वीकार करता है] = 1 चूंकि संदेश स्ट्रीम स्वीकृति को इंगित करता है, इस प्रकार दावा सच है। यदि एमपी अस्वीकार है, तो तर्क बहुत समान है।
 
आगमनात्मक परिकल्पना के लिए, हम मानते हैं कि कुछ j+1 ≤ p और किसी भी संदेश अनुक्रम Mj+1 के लिए, NMj+1 = Pr[V Mj+1 से प्रारंभ करके w को स्वीकार करता है] और फिर j और किसी भी संदेश अनुक्रम Mj के लिए परिकल्पना को सिद्ध करें .
 
यदि j सम है तो mj+1 V से P तक एक संदेश है। NMj की परिभाषा के अनुसार,


:<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>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>\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 विषम है, तो mj+1 P से V तक एक संदेश है। परिभाषा के अनुसार,
परिभाषा के अनुसार यदि j विषम है, तो m<sub>j+1</sub> P से V तक एक संदेश है:


:<math>N_{M_j} = \max\nolimits_{m_{j+1}} N_{M_{j+1}}.</math>
:<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>\max\nolimits_{m_{j+1}} * \Pr[V\text{ accepts }w\text{ starting at }M_{j+1}].</math>
यह Pr के बराबर है[V Mj से प्रारंभ करके w को स्वीकार करता है] क्योंकि:
यह <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>
: <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>
क्योंकि दाहिनी ओर का सूचक बायीं ओर की अभिव्यक्ति को अधिकतम करने के लिए संदेश mj+1 भेज सकता है। और:
क्योंकि दाहिनी ओर का सूचक बायीं ओर की अभिव्यक्ति को अधिकतम करने के लिए संदेश 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>
: <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> पूर्ण है।
चूँकि प्रोवर उसी संदेश को भेजने के अतिरिक्त कुछ नहीं कर सकता है। इस प्रकार यह मानता है कि क्या i सम या विषम है सामान्यतः इसका प्रमाण है कि <code>IP ⊆ PSPACE</code> पूर्ण है।


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


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


<nowiki>#</nowiki>SAT is a member of IP
====== एसएटी आईपी ======
हम यह दिखाकर प्रारम्भ करते हैं कि एसएटी आईपी में है,


हम यह दिखाकर शुरुआत करते हैं कि #SAT आईपी में है, जहां:
जहां:


: <math>\#\text{SAT} = \left \{ \langle \varphi, k \rangle \ : \  \varphi \text{ is a CNF-formula with exactly } k \text{ satisfying assignments} \right \}.</math>
: <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φ(x1, ..., xn) में मैप करने के लिए अंकगणितीकरण का उपयोग करते हैं, जहां उस में φ की नकल करता है यदि φ सत्य है तो 1 है और 0 अन्यथा बशर्ते कि pφ के चर को बूलियन मान निर्दिष्ट किया गया हो। φ में उपयोग किए गए बूलियन ऑपरेशन ∨, ∧ और ¬ को φ में ऑपरेटरों को प्रतिस्थापित करके में सिम्युलेटेड किया गया है जैसा कि नीचे दी गई तालिका में दिखाया गया है।
सबसे पहले हम 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"
{| border="1" cellpadding="2"
Line 86: Line 81:
|-
|-
| ¬''a'' || 1 − ''a''
| ¬''a'' || 1 − ''a''
|+ बूलियन सूत्र φ(b1, ..., bn) को बहुपद pφ(x1, ..., xn) में परिवर्तित करने के लिए अंकगणितीकरण नियम
|+ बूलियन सूत्र φ(b<sub>1</sub>, ..., b<sub>n</sub>) को पोलिनोमिअल pφ(x<sub>1</sub>, ..., x<sub>n</sub>) में परिवर्तित करने के लिए अंकगणितीय नियम
|}
|}
उदाहरण के तौर पर, φ = a ∧ (b ∨ ¬c) को निम्नानुसार बहुपद में परिवर्तित किया जाएगा:
उदाहरण के लिए φ = a ∧ (b ∨ ¬c) को निम्नानुसार पोलिनोमिअल में परिवर्तित किया जा सकता है:


:<math>\begin{align}  
:<math>\begin{align}  
Line 97: Line 92:
&= a - (ac-abc)  
&= a - (ac-abc)  
\end{align}</math>
\end{align}</math>
संक्रियाओं ab और a ∗ b में से प्रत्येक का परिणाम एक बहुपद में होता है, जिसकी डिग्री a और b के लिए बहुपद की डिग्री के योग से घिरी होती है और इसलिए, किसी भी चर की डिग्री अधिकतम φ की लंबाई होती है।
ऑपरेटर 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 में एक एकल चर ai परिभाषित करें। ≤ n और <math>a_1, \dots, a_i \in F</math> के लिए चलो
माना कि 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>  
:<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>
:ध्यान दें कि f0 का मान φ के संतोषजनक असाइनमेंट की संख्या है। f0 एक शून्य फ़ंक्शन है, जिसमें कोई चर नहीं है।
:ध्यान दें कि f<sub>0</sub> का मान φ के संतोषजनक असाइनमेंट की संख्या है। f<sub>0</sub> एक शून्य फ़ंक्शन है, जिसमें कोई वेरिएबल नहीं है।


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


* चरण 0: नीतिवचन P एक अभाज्य q > 2n चुनता है और f0 की गणना करता है, फिर यह सत्यापनकर्ता V को q और f0 भेजता है। V जाँच करता है कि q अधिकतम (1000, 2n) से बड़ा अभाज्य है और f0() = k है।
* '''फेज 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 सत्यापित करता है कि f1 की डिग्री n से कम है और f0 = f1(0) + f1(1)। (यदि नहीं तो V अस्वीकार करता है)। V अब F से P को एक यादृच्छिक संख्या r1 भेजता है।
* '''फेज 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> भेजता है।
* P, z में बहुपद के रूप में <math>f_i(r_1, \dots, r_{i-1}, z)</math> के गुणांक भेजता है। V सत्यापित करता है कि fi की डिग्री 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 को एक यादृच्छिक संख्या ri भेजता है।
* '''फेज 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 अस्वीकृत है।


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


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


चरण 0 में वी को अस्वीकार करने से रोकने के लिए, <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 को भेजने के लिए एक यादृच्छिक r1 चुनता है,
फेज 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>  
:<math>\Pr \left [\tilde f_1(r_1) = f_1(r_1) \right ] < \tfrac{1}{n^2}.</math>  
:इसका कारण यह है कि घात के एकल चर वाले बहुपद में अधिकतम d के मूल d से अधिक नहीं हो सकते हैं (जब तक कि इसका मूल्यांकन हमेशा 0 न हो)। अतः, घात के एक ही चर में अधिकतम d वाले कोई भी दो बहुपद केवल d स्थानों पर ही समान हो सकते हैं। चूंकि |एफ| > 2n r1 के इन मानों में से एक होने की संभावना अधिकतम <math>n/2^n < n/n^3</math> है यदि n > 10, या अधिकतम (n/1000) ≤ (n/n3) यदि n ≤ 10 है।
:इसका कारण यह है कि डिग्री के एकल वेरिएबल वाले पोलिनोमिअल में अधिकतम 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 if के लिए है
इस विचार को अन्य फेजों के लिए सामान्यीकृत करना हमारे पास प्रत्येक: मान 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> फिर आर के लिए<sub>i</sub>F से यादृच्छिक रूप से चुना गया,
:<math>\tilde f_{i-1}(r_1, \dots, r_{i-1}) \neq f_{i-1}(r_1, \dots, r_{i-1}),</math>  
:<math>\Pr \left [\tilde f(r_1, \dots, r_i) = f_i(r_1, \dots, r_i) \right ] \leq \tfrac{1}{n^2}.</math>  
:फिर F से यादृच्छिक रूप से चुने गए r<sub>i</sub> के लिए,
:वहाँ n चरण हैं, इसलिए संभावना है कि <math>\tilde P</math> भाग्यशाली है क्योंकि V किसी चरण में एक सुविधाजनक ri का चयन करता है जो अधिकतम 1/n है। इसलिए, कोई भी सूचक सत्यापनकर्ता को 1/n से अधिक संभावना के साथ स्वीकार करने के लिए बाध्य नहीं कर सकता है। हम परिभाषा से यह भी देख सकते हैं कि सत्यापनकर्ता V संभाव्य बहुपद समय में काम करता है। इस प्रकार, #SAT ∈ IP.
:<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>PSPACE ⊆ IP</code> यहां प्रदर्शित प्रमाण तकनीक का श्रेय [[आदि शमीर]] को दिया जाता है।


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


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


: <math>f_i(a_1, \dots, a_i) =  \begin{cases}
: <math>f_i(a_1, \dots, a_i) =  \begin{cases}
Line 136: Line 132:
0 & \text{otherwise}
0 & \text{otherwise}
\end{cases} </math>
\end{cases} </math>
यहाँ, φ(<sub>1</sub>, ..., <sub>i</sub>) ए के साथ φ है<sub>1</sub> एक को<sub>i</sub>x के स्थान पर प्रतिस्थापित<sub>1</sub> एक्स को<sub>i</sub>. इस प्रकार एफ<sub>0</sub> ψ का सत्य मान है। ψ का अंकगणित करने के लिए हमें निम्नलिखित नियमों का उपयोग करना चाहिए:
यहां φ(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 \\
:<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 \\
Line 143: Line 139:
जबकि पहले हम x * y = 1 − (1 − x)(1 − y) परिभाषित करते थे।
जबकि पहले हम x * y = 1 − (1 − x)(1 − y) परिभाषित करते थे।


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


तो अब इससे पहले कि हम अंकगणित करें <math>\psi = \mathsf Q_1x_1\dots \mathsf Q_mx_m[\varphi]</math> हम एक नई अभिव्यक्ति प्रस्तुत करते हैं:
तो अब इससे पहले कि हम <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 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>
: <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>, ..., एक्स<sub>m</sub>) जो φ का अंकगणित करके प्राप्त किया जाता है। अब बहुपद की घात को कम रखने के लिए, हम f को परिभाषित करते हैं<sub>i</sub>एफ के संदर्भ में<sub>i+1</sub>:
अब प्रत्येक 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} = \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} = \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>
:<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, बहुपद की डिग्री को नहीं बदलती है। यह भी देखना जरूरी है कि आर<sub>x</sub>ऑपरेशन बूलियन इनपुट पर फ़ंक्शन का मान नहीं बदलता है। तो एफ<sub>0</sub> अभी भी ψ का सत्य मान है, लेकिन R<sub>x</sub>मान एक ऐसा परिणाम उत्पन्न करता है जो x में रैखिक होता है। किसी के बाद भी <math>\mathsf Q_i x_i</math> हम जोड़ते हैं <math>\mathrm R_{x_1}\dots \mathrm R_{x_i}</math> अंकगणित के बाद डिग्री को 1 तक कम करने के लिए ψ′ में <math>\mathsf Q_i</math>.
अब हम देख सकते हैं कि कमी ऑपरेशन R पोलिनोमिअल की डिग्री को नहीं परिवर्तित होती है। यह भी देखना महत्वपूर्ण है कि आरएक्स ऑपरेशन बूलियन इनपुट पर फ़ंक्शन के मान को नहीं परिवर्तित करता है। तो f<sub>0</sub> अभी भी ψ का सत्य मान है, लेकिन 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, ψ की लंबाई है, तो प्रोटोकॉल में सभी अंकगणितीय ऑपरेशन कम से कम n<sup>4</sup> आकार के क्षेत्र पर होते हैं जहां n ψ की लंबाई है।
 
अब प्रोटोकॉल का वर्णन करते हैं। यदि n ψ की लंबाई है, तो प्रोटोकॉल में सभी अंकगणितीय ऑपरेशन कम से कम n आकार के क्षेत्र पर होते हैं<sup>4</sup> जहां n ψ की लंबाई है।


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


* चरण I: ''पी'' → ''वी'': ''पी'' भेजता है <math>f_i(r_1,\dots,r_{i-1},z)</math> z में एक बहुपद के रूप में। आर<sub>1</sub> के लिए पहले से निर्धारित यादृच्छिक मानों को दर्शाता है <math>r_1,\dots,r_{i-1}</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 है और निम्नलिखित समीकरण सत्य हैं:
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 \\
:<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.
f_{i}(r_1,\dots,r_{i-1},0) * f_i(r_1, \dots,r_{i-1},1) & \mathsf S = \exists.
\end{cases}</math>
\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>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 को प्रतिस्थापित कर देता है)।
''V'' ''P'': ''V ,'' ''F'' में एक यादृच्छिक r चुनता है और इसे P को भेजता है। (यदि <math>\mathsf S=\mathrm R</math> तो यह r पिछले r को प्रतिस्थापित करता है)।


चरण i +1 पर जाएं जहां P को V को इस बात के लिए राजी करना होगा <math>f_i(r_1,\dots,r)</math> सही है।
फेज 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 अस्वीकार कर देता है। यह प्रोटोकॉल विवरण का अंत है.
* '''फेज ''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 को तब स्वीकृत किया जा सकता है जब 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> ​​भी संभवतः गलत होंगे। कुछ यादृच्छिक r पर प्रोबेबिलिटी होने के लिए <math> \tilde{P} </math> की संभावना क्षेत्र आकार <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> ध्यान दें कि क्वाड्राटिक रेसीड्यूसीटी (क्यूएनआर) संभवतः ग्राफ आइसोमोर्फिज्म की तुलना में एक साधारण समस्या है क्योंकि क्वाड्राटिक रेसीड्यूसीटी <code>UP</code> इंटरसेक्ट <code>co-UP</code> में है।<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-->
Line 242: Line 235:


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


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 maint]]
[[Category:Collapse templates]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:प्रमाण युक्त लेख]]
[[Category:संभाव्य जटिलता वर्ग]]

Latest revision as of 15:08, 30 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 है और निम्नलिखित समीकरण सत्य हैं:

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

VP: V , F में एक यादृच्छिक r चुनता है और इसे P को भेजता है। (यदि तो यह r पिछले r को प्रतिस्थापित करता है)।

फेज i +1 पर जाएं जहां P को V को समझाना होगा कि सही है।

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

यदि ψ सत्य है तो V को तब स्वीकृत किया जा सकता है जब V, P प्रोटोकॉल का प्रयोग करता है। इसी प्रकार यदि एक मॉलिसियस प्रोवर है जो असत्य है और यदि ψ गलत है, तो को फेज 0 पर f0 के लिए कुछ मान भेजने की आवश्यकता होगी। यदि फेज i पर, V में के लिए गलत मान है तो और ​​भी संभवतः गलत होंगे। कुछ यादृच्छिक r पर प्रोबेबिलिटी होने के लिए की संभावना क्षेत्र आकार द्वारा विभाजित पोलिनोमिअल की अधिकतम डिग्री है। प्रोटोकॉल O(n2) फेजों के माध्यम से चलता है, इसलिए किसी फेज़ में के प्रोबेबिलिटी होने की संभावना ≤ 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] ध्यान दें कि क्वाड्राटिक रेसीड्यूसीटी (क्यूएनआर) संभवतः ग्राफ आइसोमोर्फिज्म की तुलना में एक साधारण समस्या है क्योंकि क्वाड्राटिक रेसीड्यूसीटी UP इंटरसेक्ट co-UP में है।[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.


संदर्भ