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

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

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

एमए

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

फॉर्मेट रूप से, कॉम्पलेक्सिटी वर्ग 'एमए' डिसिशन प्रॉब्लम्स का ग्रुप है, जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है जहां मर्लिन का एकमात्र उपाय आर्थर द्वारा किसी भी कैलकुलेशन से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L 'एमए' में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन 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 वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड हुआ है।

एएम

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

दूसरे शब्दों में, लैंग्वेज L एएम में है यदि पोलीनोमिअल-टाइम नियतात्मक ट्यूरिंग मशीन 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 वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड है।

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

गुण

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

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

ग्रन्थसूची

• 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