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

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

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

एमए

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

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

जटिलता वर्ग एएम (या एएम [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' 'AM[2]' है। 'एएम[3]' की शुरुआत मर्लिन से आर्थर के लिए संदेश से होगी, फिर आर्थर से मर्लिन के लिए संदेश और फिर अंत में मर्लिन से आर्थर के लिए संदेश के साथ। अंतिम संदेश हमेशा मर्लिन की ओर से आर्थर के लिए होना चाहिए, क्योंकि आर्थर के लिए अपना उत्तर निश्चित करने के बाद मर्लिन को संदेश भेजने से कभी मदद नहीं मिलती।

गुण

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

• किसी भी स्थिरांक k ≥ 2 के लिए, वर्ग 'AM[k]' 'AM[2]' के बराबर है। यदि k को इनपुट आकार से बहुपद रूप से संबंधित किया जा सकता है, तो वर्ग 'AM'[poly(n)] वर्ग, 'IP (जटिलता)' के बराबर है, जिसे 'PSPACE' के बराबर माना जाता है और व्यापक रूप से वर्ग 'AM[2]' से अधिक मजबूत माना जाता है।
• 'AM' में 'MA' समाहित है, क्योंकि 'AM'[3] में 'MA' शामिल है: आर्थर, मर्लिन का प्रमाणपत्र प्राप्त करने के बाद, आवश्यक संख्या में सिक्के उछाल सकता है, उन्हें मर्लिन को भेज सकता है, और प्रतिक्रिया को अनदेखा कर सकता है।
• यह खुला है कि क्या 'एएम' और 'एमए' अलग हैं। प्रशंसनीय सर्किट निचली सीमा के तहत ('पी' = 'बीपीपी' के समान), वे दोनों 'एनपी' के बराबर हैं।
• AM क्लास BP⋅NP के समान है जहां BP बाउंडेड-एरर प्रोबेबिलिस्टिक ऑपरेटर को दर्शाता है। भी,$\exists \cdot {\mathsf {BPP}}$(ExistsBPP के रूप में भी लिखा जाता है) एमए का उपसमूह है। क्या एमए के बराबर है$\exists \cdot {\mathsf {BPP}}$ खुला प्रश्न है.
• निजी सिक्का प्रोटोकॉल में रूपांतरण, जिसमें मर्लिन आर्थर के यादृच्छिक निर्णयों के नतीजे की भविष्यवाणी नहीं कर सकता है, सामान्य मामले में बातचीत के दौर की संख्या अधिकतम 2 तक बढ़ा देगा। तो AM का निजी-सिक्का संस्करण सार्वजनिक-सिक्का संस्करण के बराबर है।
• एमए में एनपी (जटिलता) और बीपीपी (जटिलता) दोनों शामिल हैं। बीपीपी के लिए यह तत्काल है, क्योंकि आर्थर मर्लिन को आसानी से अनदेखा कर सकता है और समस्या को सीधे हल कर सकता है; एनपी के लिए, मर्लिन को केवल आर्थर को प्रमाणपत्र भेजने की आवश्यकता है, जिसे आर्थर बहुपद समय में नियतात्मक रूप से मान्य कर सकता है।
• एमए और एएम दोनों बहुपद पदानुक्रम में समाहित हैं। विशेष रूप से, एमए Σ के प्रतिच्छेदन में निहित है₂^पीऔर Π₂^P और AM Π में निहित है₂^पी. इससे भी अधिक, MA उपवर्ग S2P (जटिलता)| में समाहित हैS^P
  ₂, सममित प्रत्यावर्तन को व्यक्त करने वाला जटिलता वर्ग। यह सिप्सर-लॉटमैन प्रमेय का सामान्यीकरण है।
• एएम एनपी/पॉली में समाहित है, जो बहुपद आकार सलाह (जटिलता) के साथ गैर-नियतात्मक बहुपद समय में गणना योग्य निर्णय समस्याओं का वर्ग है। प्रमाण P/poly#Adleman's theorem|Adleman's theorem का रूपांतर है।
• एमए पीपी (जटिलता) में निहित है; यह परिणाम वीरशैचिन के कारण है।
• एमए इसके क्वांटम संस्करण, क्यूएमए में निहित है।
• एएम में यह निर्णय लेने की ग्राफ समरूपता समस्या शामिल है कि क्या दो ग्राफ समरूपी नहीं हैं। निजी सिक्कों का उपयोग करने वाला प्रोटोकॉल निम्नलिखित है और इसे सार्वजनिक सिक्का प्रोटोकॉल में बदला जा सकता है। दो ग्राफ जी और एच दिए गए हैं, आर्थर यादृच्छिक रूप से उनमें से को चुनता है, और इसके शीर्षों का यादृच्छिक क्रमचय चुनता है, मर्लिन को क्रमबद्ध ग्राफ आई प्रस्तुत करता है। मर्लिन को जवाब देना होगा कि क्या I G या H से बना है। यदि ग्राफ़ गैर-समरूपी हैं, तो मर्लिन पूर्ण निश्चितता के साथ उत्तर देने में सक्षम होंगे (यह जांच कर कि क्या I G के समरूपी है)। चूँकि , यदि ग्राफ समरूपी हैं, तो यह संभव है कि जी या एच का उपयोग आई बनाने के लिए किया गया था, और समान रूप से संभव है। इस मामले में, मर्लिन के पास उन्हें अलग बताने का कोई तरीका नहीं है और वह आर्थर को अधिकतम 1/2 संभावना के साथ मना सकता है, और इसे दोहराव द्वारा 1/4 तक बढ़ाया जा सकता है। यह वास्तव में शून्य ज्ञान प्रमाण है।
• यदि AM में coNP है तो बहुपद पदानुक्रम = AM। यह इस बात का प्रमाण है कि ग्राफ समरूपता एनपी-पूर्ण होने की संभावना नहीं है, क्योंकि इसका तात्पर्य बहुपद पदानुक्रम के पतन से है।
• विस्तारित रीमैन परिकल्पना को मानते हुए, यह ज्ञात है कि किसी भी डी समस्या के लिए बहुभिन्नरूपी बहुपदों का संग्रह दिया गया है $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