आर्थर-मर्लिन प्रोटोकॉल

कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी में, बाबई (1985), द्वारा प्रस्तुत किया गया आर्थर-मर्लिन प्रोटोकॉल, ऐसा इंटरैक्टिव प्रूफ सिस्टम है जिसमें वेरिफायर के कॉइन टोसेस को पब्लिक करने के लिए कन्स्ट्रैनड किया जाता है (अर्थात इसकी इनफार्मेशन होती है)। गोल्डवेसर & सिप्सर (1986) ने वेरीफाई किया कि प्राइवेट कॉइन के साथ इच्छानुसार लंबाई के इंटरैक्टिव प्रूफ वाली सभी (फॉर्मेट) लैंग्वेजेज में पब्लिक कॉइन के साथ भी इंटरैक्टिव प्रूफ होते हैं।

प्रोटोकॉल में क्रमशः आर्थर और मर्लिन नामक दो पार्टिसिपेंट्स को देखते हुए, मूल धारणा यह है कि आर्थर स्टैण्डर्ड कंप्यूटर (या वेरिफायर) है जो रैंडम नंबर उत्पन्न करने वाली डिवाइस है, यद्यपि मर्लिन प्रभावी रूप से इनफाइनाइट कम्प्यूटेशनल पॉवर वाला ओरेकल है (जिसे प्रोवर के रूप में भी जाना जाता है)। चूँकि, मर्लिन आवश्यक रूप से सत्यवादी नहीं है, इसलिए आर्थर को आर्थर के प्रश्नों के उत्तर में मर्लिन द्वारा प्रदान की गई इनफार्मेशन को एनालाइज़ करना चाहिए और प्रॉब्लम का डिसिशन स्वयं करना चाहिए। इस प्रोटोकॉल द्वारा प्रॉब्लम को सॉल्व करने योग्य माना जाता है यदि जब भी उत्तर हाँ होता है, तो मर्लिन के निकट रेस्पॉन्स की कुछ सीरीज होती है जो आर्थर को कम से कम 2⁄3 टाइम एक्सेप्ट करना पड़ता है, और यदि जब भी उत्तर नहीं होता है, तो आर्थर कभी भी 1⁄3 से अधिक टाइम एक्सेप्ट नहीं करता है। इस प्रकार, आर्थर प्रोबबिलिस्टिक पोलीनोमिअल-टाइम वेरिफायर के रूप में फंक्शन करता है, यह मानते हुए कि उसे अपने डिसिशन और प्रश्न पूछने के लिए पोलीनोमिअल टाइम अलॉट किया गया है।

MA

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

फॉर्मेट रूप से, कॉम्पलेक्सिटी क्लास 'MA ' डिसिशन प्रॉब्लम्स का ग्रुप है, जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है जहां मर्लिन का एकमात्र उपाय आर्थर द्वारा किसी भी कैलकुलेशन से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L 'MA ' में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन M और पोलीनोमिअल p, q उपस्थित है जैसे कि लंबाई के प्रत्येक इनपुट स्ट्रिंग x के लिए n = |x| है।

• यदि x, L में है, तो $\exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3$ प्राप्त होता है।
• यदि x, L में नहीं है, तो $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3$ प्राप्त होता है।

दूसरे नियम को वैकल्पिक रूप से इस प्रकार लिखा जा सकता है:

• यदि x, L में नहीं है, तो $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3$ प्राप्त होता है।

उपरोक्त अनौपचारिक परिभाषा के साथ इसकी अपेक्षा करने के लिए, z मर्लिन का कथित प्रूफ है (जिसका साइज पोलीनोमिअल से बॉण्डेड है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड हुआ है।

AM

कॉम्पलेक्सिटी क्लास AM (या AM [2]) डिसिशन प्रॉब्लम्स का ग्रुप है जिसे दो मैसेज के साथ आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है। केवल प्रश्न या रनिंग डिवाइस है: आर्थर कुछ रैंडम कॉइन टॉस करता है और अपने कॉइन टोसेस के सभी परिणामों का परिणाम मर्लिन को प्रदान करता है, मर्लिन कथित प्रूफ के साथ उत्तर देता है, और आर्थर कन्फर्म रूप से प्रूफ की पुष्टि करता है। इस प्रोटोकॉल में, आर्थर को केवल कॉइन टोसेस के परिणाम मर्लिन को प्रदान करने की अनुमति है, और अंतिम चरण में आर्थर को केवल अपने पूर्व से उत्पन्न रैंडम कॉइन फ्लिप और मर्लिन के मैसेज का उपयोग करके यह डिसिशन लेना होगा कि उसे एक्सेप्ट करना है या रिजेक्ट करना है।

दूसरे शब्दों में, लैंग्वेज L AM में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन M और पोलीनोमिअल p, q उपस्थित है जैसे कि प्रत्येक इनपुट स्ट्रिंग x लंबाई के लिए n = |x| है।

• यदि x L में है, तो $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3$ प्राप्त होता है।
• यदि x, L में नहीं है, तो $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3$ प्राप्त होता है।

यहां दूसरे नियम को इस प्रकार पुनः लिखा जा सकता है:

• यदि x, L में नहीं है, तो $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3$ प्राप्त होता है।

जैसा कि ऊपर दिया गया है, z मर्लिन का कथित प्रूफ है (जिसका साइज पोलीनोमिअल से बॉण्डेड है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड है।

कॉम्पलेक्सिटी क्लास 'AM[k]' प्रॉब्लम्स का ग्रुप है जिसे k प्रश्नों और रेस्पॉन्स के साथ पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है। जैसा कि ऊपर परिभाषित है 'AM' 'AM[2]' है। 'AM[3]' का प्रारम्भ मर्लिन से आर्थर के लिए मैसेज के साथ होगी, फिर आर्थर से मर्लिन के लिए मैसेज और फिर अंत में मर्लिन से आर्थर के लिए मैसेज के साथ होता है। अंतिम मैसेज सदैव मर्लिन की ओर से आर्थर के लिए होना चाहिए, क्योंकि आर्थर के लिए अपना उत्तर कन्फर्म करने के पश्चात मर्लिन को मैसेज सेंड करने से कभी हेल्प नहीं मिलती है।

गुण

• MA और AM दोनों अपरिवर्तित रहते हैं यदि उनकी परिभाषाओं को पूर्णता की आवश्यकता के लिए परिवर्तित कर दिया जाता है, जिसका अर्थ है कि आर्थर प्रोबेबिलिटी 1 (2/3 के अतिरिक्त) को एक्सेप्ट करता है जब x लैंग्वेज में होता है।

• किसी भी कांस्टेंट k ≥ 2 के लिए, क्लास 'AM[k]' 'AM[2]' के समान है। यदि k को इनपुट साइज से पोलीनोमिअल रूप से संबंधित किया जा सकता है, तो क्लास 'AM'[poly(n)] क्लास, आईपी के समान है, जिसे 'पीस्पेस' के समान माना जाता है और व्यापक रूप से क्लास 'AM[2]' से अधिक स्ट्रांग माना जाता है।
• 'AM' में 'MA' कॉन्टैनेड है, क्योंकि 'AM'[3] में 'MA' सम्मिलित है: आर्थर, मर्लिन का सर्टिफिकेट प्राप्त करने के पश्चात, आवश्यक नंबर में कॉइन से टॉस कर सकता है, उन्हें मर्लिन को सेंड कर सकता है, और प्रतिक्रिया को इग्नोर कर सकता है।
• यह ओपन है कि क्या 'AM' और 'MA' भिन्न-भिन्न हैं। प्लॉसिबल सर्किट लोअर बाउंड के अनुसार (P=BPP के समान), वे दोनों 'NP' के समान हैं।
• AM क्लास BP-NP के समान है जहां BP बाउंडेड-एरर प्रोबेबिलिस्टिक ऑपरेटर को प्रदर्शित करता है। $\exists \cdot {\mathsf {BPP}}$(जिसे एक्सिस्ट्सबीपीपी के रूप में भी लिखा जाता है) भी MA का सबसेट है। क्या MA के समान है $\exists \cdot {\mathsf {BPP}}$ ओपन प्रश्न है।
• प्राइवेट कॉइन प्रोटोकॉल में रूपांतरण, जिसमें मर्लिन आर्थर के रैंडम निर्णयों के प्रणाम की भविष्यवाणी नहीं कर सकता है, सामान्य स्थिति में इंटरैक्शन के टाइम की नंबर अधिकतम 2 तक बढ़ा देता है। तो AM का प्राइवेट-कॉइन वर्जन पब्लिक-कॉइन वर्जन के समान है।
• MA में NP और BPP दोनों सम्मिलित हैं। BPP के लिए यह इमीडियेड है, क्योंकि आर्थर मर्लिन को सरलता से इग्नोर कर सकता है और प्रॉब्लम का सीधे सॉल्व कर सकता है; NP के लिए, मर्लिन को केवल आर्थर को सर्टिफिकेट प्रदान करने की आवश्यकता है, जिसे आर्थर पोलीनोमिअल टाइम में डेटर्मीनिस्टिक रूप से मान्य कर सकता है।
• MA और AM दोनों पोलीनोमिअल हायरार्की में समाहित हैं। विशेष रूप से, MA Σ₂^P और Π₂^P के इंटरसेक्शन में कॉन्टैनेड है और AM Π₂^P में कॉन्टैनेड है। इससे भी अधिक, MA सबक्लास S^P
  ₂ में समाहित है, कॉम्पलेक्सिटी क्लास जो सिमेट्रिक अलटरनेशन को व्यक्त करता है। यह सिप्सर-लॉटमैन प्रमेय का सामान्यीकरण है।
• AM NP/पॉली में समाहित है, जो पोलीनोमिअल साइज एडवाइस के साथ अन्य-डेटर्मीनिस्टिक पोलीनोमिअल टाइम में कैलकुलेशन योग्य डिसिशन प्रॉब्लम्स का क्लास है। प्रूफ एडलमैन के प्रमेय का रूपांतर है।
• MA PP में कॉन्टैनेड है; यह परिणाम वीरशैचिन के कारण है।
• MA इसके क्वांटम वर्जन, क्यूएमए में कॉन्टैनेड है।
• AM में यह डिसिशन लेने की प्रॉब्लम है कि क्या दो ग्राफ समरूपी नहीं हैं। प्राइवेट कॉइन का उपयोग करने वाला प्रोटोकॉल निम्नलिखित है और इसे पब्लिक कॉइन प्रोटोकॉल में परिवर्तित किया जा सकता है। दो ग्राफ G और H दिए गए हैं, आर्थर रैंडम रूप से उनमें से एक का चयन करता है, और इसके शीर्षों का रैंडम पेरमुटेशन चयनित करता है, सॉर्टेड ग्राफ I को मर्लिन के सामने प्रस्तुत करता है। मर्लिन को उत्तर देना होगा कि क्या I G या H से बना है। यदि ग्राफ़ अन्य-समरूपी हैं, तो मर्लिन पूर्ण निश्चितता के साथ उत्तर देने में सक्षम होंगे (यह परीक्षण करके कि क्या I G के समरूपी है)। चूँकि, यदि ग्राफ समरूपी हैं, तो यह संभव है कि I बनाने के लिए G या H का उपयोग किया गया था, और यह समान रूप से संभव है। इस स्थिति में, मर्लिन के पास उन्हें भिन्न बताने की कोई विधि नहीं है और वह आर्थर को अधिकतम 1/2 प्रोबेबिलिटी के साथ मना सकता है, और इसे रेपेटिशन द्वारा 1/4 तक बढ़ाया जा सकता है। यह वास्तव में जीरो नॉलेज प्रूफ है।
• यदि AM में coNP है PH = AM है। यह इस विषय का प्रूफ है कि ग्राफ समरूपता NP-पूर्ण होने की प्रोबेबिलिटी नहीं है, क्योंकि इसका तात्पर्य पोलीनोमिअल हायरार्की के कॉल्लाप्स से है।
• यह ज्ञात है, ईआरएच मानते हुए, कि किसी भी d प्रॉब्लम के लिए मल्टीवैरियट पोलीनोमिकल्स का संग्रह दिया गया है $f_{i}$ प्रत्येक पूर्णांक गुणांक और अधिकतम d डिग्री के साथ, क्या उनके निकट सामान्य सम्मिश्र शून्य है? 'AM' में है।

ग्रन्थसूची

• Babai, László (1985), "Trading group theory for randomness", STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, pp. 421–429, ISBN 978-0-89791-151-1.
• Goldwasser, Shafi; Sipser, Michael (1986), "Private coins versus public coins in interactive proof systems", STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, ACM, pp. 59–68, ISBN 978-0-89791-193-1.
• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4.
• Madhu Sudan's MIT course on advanced complexity

बाहरी संबंध

• Complexity Zoo: MA
• Complexity Zoo: AM