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

कम्प्यूटेशनल समष्टिता सिद्धांत में, बाबई (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