आर्थर-मर्लिन प्रोटोकॉल: Difference between revisions

Revision as of 19:24, 14 September 2023

कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी में, बाबई (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 लैंग्वेज में होता है।^[1]

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

संदर्भ

↑ For a proof, see Rafael Pass and Jean-Baptiste Jeannin (March 24, 2009). "Lecture 17: Arthur-Merlin games, Zero-knowledge proofs" (PDF). Retrieved June 23, 2010.
↑ Impagliazzo, Russell; Wigderson, Avi (1997-05-04). P = BPP if E requires exponential circuits: derandomizing the XOR lemma. ACM. pp. 220–229. doi:10.1145/258533.258590. ISBN 0897918886. S2CID 18921599.
↑ "सममित प्रत्यावर्तन BPP को कैप्चर करता है" (PDF). Ccs.neu.edu. Retrieved 2016-07-26.
↑ Vereschchagin, N.K. (1992). "On the power of PP". [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference. pp. 138–143. doi:10.1109/sct.1992.215389. ISBN 081862955X. S2CID 195705029.
↑ Vidick, Thomas; Watrous, John (2016). "क्वांटम प्रमाण". Foundations and Trends in Theoretical Computer Science. 11 (1–2): 1–215. arXiv:1610.01664. doi:10.1561/0400000068. ISSN 1551-305X. S2CID 54255188.
↑ "Course: Algebra and Computation". People.csail.mit.edu. Retrieved 2016-07-26.

ग्रन्थसूची

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

[1] For a proof, see Rafael Pass and Jean-Baptiste Jeannin (March 24, 2009). "Lecture 17: Arthur-Merlin games, Zero-knowledge proofs" (PDF). Retrieved June 23, 2010.

[2] Impagliazzo, Russell; Wigderson, Avi (1997-05-04). P = BPP if E requires exponential circuits: derandomizing the XOR lemma. ACM. pp. 220–229. doi:10.1145/258533.258590. ISBN 0897918886. S2CID 18921599.

[3] "सममित प्रत्यावर्तन BPP को कैप्चर करता है" (PDF). Ccs.neu.edu. Retrieved 2016-07-26.

[4] Vereschchagin, N.K. (1992). "On the power of PP". [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference. pp. 138–143. doi:10.1109/sct.1992.215389. ISBN 081862955X. S2CID 195705029.

[5] Vidick, Thomas; Watrous, John (2016). "क्वांटम प्रमाण". Foundations and Trends in Theoretical Computer Science. 11 (1–2): 1–215. arXiv:1610.01664. doi:10.1561/0400000068. ISSN 1551-305X. S2CID 54255188.

[6] "Course: Algebra and Computation". People.csail.mit.edu. Retrieved 2016-07-26.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 2: / Line 2: @@
 [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी]] में, {{Harvtxt|बाबई |1985}}, द्वारा प्रस्तुत किया गया '''आर्थर-मर्लिन प्रोटोकॉल''', ऐसा [[इंटरैक्टिव प्रमाण प्रणाली|इंटरैक्टिव प्रूफ सिस्टम]] है जिसमें वेरिफायर के सिक्के उछालने को सार्वजनिक करने के लिए बाध्य किया जाता है (अर्थात इसकी इनफार्मेशन होती है)। {{Harvtxt|गोल्डवेसर |सिप्सर |1986}} ने प्रमाणित किया कि निजी सिक्कों के साथ इच्छानुसार लंबाई के इंटरैक्टिव प्रूफ वाली सभी (फॉर्मेट) [[औपचारिक भाषा|लैंग्वेजेज]] में सार्वजनिक सिक्कों के साथ भी इंटरैक्टिव प्रूफ होते हैं।
-प्रोटोकॉल में क्रमशः आर्थर और मर्लिन नामक दो पार्टिसिपेंट्स को देखते हुए, मूल धारणा यह है कि आर्थर स्टैण्डर्ड कंप्यूटर (या वेरिफायर) है जो [[यादृच्छिक संख्या पीढ़ी|रैंडम नंबर]] उत्पन्न करने वाली डिवाइस है, यद्यपि मर्लिन प्रभावी रूप से इनफाइनाइट कम्प्यूटेशनल पॉवर वाला ओरेकल है (जिसे प्रोवर के रूप में भी जाना जाता है)। चूँकि, मर्लिन आवश्यक रूप से सत्यवादी नहीं है, इसलिए आर्थर को आर्थर के प्रश्नों के उत्तर में मर्लिन द्वारा प्रदान की गई इनफार्मेशन को एनालाइज़ करना चाहिए और प्रॉब्लम का निर्णय स्वयं करना चाहिए। इस प्रोटोकॉल द्वारा प्रॉब्लम को सॉल्व करने योग्य माना जाता है यदि जब भी उत्तर हाँ होता है, तो मर्लिन के निकट रेस्पॉन्स की कुछ सीरीज होती है जो आर्थर को कम से कम {{frac|2|3}} समय स्वीकार करना पड़ता है, और यदि जब भी उत्तर नहीं होता है, तो आर्थर कभी भी {{frac|1|3}} से अधिक समय स्वीकार नहीं करता है। इस प्रकार, आर्थर प्रोबबिलिस्टिक पोलीनोमिअल-टाइम वेरिफायर के रूप में फंक्शन करता है, यह मानते हुए कि उसे अपने निर्णय और प्रश्न पूछने के लिए पोलीनोमिअल टाइम अलॉट किया गया है।
+प्रोटोकॉल में क्रमशः आर्थर और मर्लिन नामक दो पार्टिसिपेंट्स को देखते हुए, मूल धारणा यह है कि आर्थर स्टैण्डर्ड कंप्यूटर (या वेरिफायर) है जो [[यादृच्छिक संख्या पीढ़ी|रैंडम नंबर]] उत्पन्न करने वाली डिवाइस है, यद्यपि मर्लिन प्रभावी रूप से इनफाइनाइट कम्प्यूटेशनल पॉवर वाला ओरेकल है (जिसे प्रोवर के रूप में भी जाना जाता है)। चूँकि, मर्लिन आवश्यक रूप से सत्यवादी नहीं है, इसलिए आर्थर को आर्थर के प्रश्नों के उत्तर में मर्लिन द्वारा प्रदान की गई इनफार्मेशन को एनालाइज़ करना चाहिए और प्रॉब्लम का डिसिशन स्वयं करना चाहिए। इस प्रोटोकॉल द्वारा प्रॉब्लम को सॉल्व करने योग्य माना जाता है यदि जब भी उत्तर हाँ होता है, तो मर्लिन के निकट रेस्पॉन्स की कुछ सीरीज होती है जो आर्थर को कम से कम {{frac|2|3}} टाइम एक्सेप्ट करना पड़ता है, और यदि जब भी उत्तर नहीं होता है, तो आर्थर कभी भी {{frac|1|3}} से अधिक टाइम एक्सेप्ट नहीं करता है। इस प्रकार, आर्थर प्रोबबिलिस्टिक पोलीनोमिअल-टाइम वेरिफायर के रूप में फंक्शन करता है, यह मानते हुए कि उसे अपने डिसिशन और प्रश्न पूछने के लिए पोलीनोमिअल टाइम अलॉट किया गया है।
 ==एमए==
-ऐसा सबसे सरल प्रोटोकॉल 1-संदेश प्रोटोकॉल है जो मर्लिन आर्थर को संदेश प्रेक्षित करता है, और फिर आर्थर संभाव्य बहुपद समय गणना चलाकर निर्णय लेता है कि उसे स्वीकार करना है या नहीं है। (यह एनपी की वेरिफायर-आधारित परिभाषा के समान है, एकमात्र अंतर यह है कि आर्थर को यहां यादृच्छिकता का उपयोग करने की अनुमति है।) इस प्रोटोकॉल में मर्लिन के पास आर्थर के सिक्के उछालने की सुविधा नहीं है, क्योंकि यह एकल-संदेश प्रोटोकॉल है और मर्लिन का संदेश प्राप्त करने के पश्चात ही आर्थर अपने सिक्के उछालता है। इस प्रोटोकॉल को एमए कहा जाता है। अनौपचारिक रूप से, लैंग्वेज L 'एमए' में है यदि लैंग्वेज में सभी स्ट्रिंग्स के लिए, बहुपद आकार का प्रूफ है कि मर्लिन उच्च संभावना के साथ आर्थर को इस तथ्य को समझाने के लिए प्रेक्षित कर सकता है, और लैंग्वेज में नहीं सभी स्ट्रिंग्स के लिए कोई प्रूफ नहीं है जो उच्च संभावना के साथ आर्थर को आश्वस्त करता है।
+ऐसा सबसे सरल प्रोटोकॉल 1-मैसेज प्रोटोकॉल है जो मर्लिन आर्थर को मैसेज सेंड करता है, और फिर आर्थर प्रोबबिलिस्टिक पोलीनोमिअल टाइम कैलकुलेशन चलाकर डिसिशन लेता है कि उसे एक्सेप्ट करना है या नहीं है। (यह एनपी की वेरिफायर-बेस्ड परिभाषा के समान है, एकमात्र अंतर यह है कि आर्थर को यहां रैंडम का उपयोग करने की अनुमति है।) इस प्रोटोकॉल में मर्लिन के पास आर्थर के सिक्के उछालने की सुविधा नहीं है, क्योंकि यह एकल-मैसेज प्रोटोकॉल है और मर्लिन का मैसेज प्राप्त करने के पश्चात ही आर्थर अपने सिक्के उछालता है। इस प्रोटोकॉल को एमए कहा जाता है। इन्फॉर्मली रूप से, लैंग्वेज L 'एमए' में है यदि लैंग्वेज में सभी स्ट्रिंग्स के लिए, पोलीनोमिअल साइज का प्रूफ है कि मर्लिन उच्च प्रोबेबिलिटी के साथ आर्थर को इस तथ्य को समझाने के लिए सेंड कर सकता है, और लैंग्वेज में नहीं सभी स्ट्रिंग्स के लिए कोई प्रूफ नहीं है जो उच्च प्रोबेबिलिटी के साथ आर्थर को कन्फर्म करता है।
-फॉर्मेट रूप से, कॉम्पलेक्सिटी वर्ग '''<nowiki/>'एमए'<nowiki/>''' निर्णय समस्याओं का समूह है जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा बहुपद समय में निश्चित किया जा सकता है जहां मर्लिन का एकमात्र उपाय आर्थर द्वारा किसी भी गणना से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L '''<nowiki/>'एमए'''' में है यदि बहुपद-समय नियतात्मक ट्यूरिंग मशीन M और बहुपद p, q उपस्थित है जैसे कि लंबाई के प्रत्येक इनपुट स्ट्रिंग x के लिए n = |x| है।
+फॉर्मेट रूप से, कॉम्पलेक्सिटी वर्ग '''<nowiki/>'एमए'<nowiki/>''' डिसिशन प्रॉब्लम्स का ग्रुप है, जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है जहां मर्लिन का एकमात्र उपाय आर्थर द्वारा किसी भी कैलकुलेशन से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L '''<nowiki/>'एमए'''' में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन M और पोलीनोमिअल p, q उपस्थित है जैसे कि लंबाई के प्रत्येक इनपुट स्ट्रिंग x के लिए n = |x| है।
 *यदि x, L में है, तो <math>\exists z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\ge2/3</math> प्राप्त होता है।
 *यदि x, L में नहीं है, तो <math>\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=0)\ge2/3</math> प्राप्त होता है।
 दूसरे नियम को वैकल्पिक रूप से इस प्रकार लिखा जा सकता है:
 *यदि x, L में नहीं है, तो <math>\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\le1/3</math> प्राप्त होता है।
-उपरोक्त अनौपचारिक परिभाषा के साथ इसकी अपेक्षा करने के लिए, z मर्लिन का कथित प्रूफ है (जिसका आकार बहुपद से घिरा हुआ है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो बहुपद से भी घिरा हुआ है।
+उपरोक्त अनौपचारिक परिभाषा के साथ इसकी अपेक्षा करने के लिए, z मर्लिन का कथित प्रूफ है (जिसका साइज पोलीनोमिअल से बॉण्डेड है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड हुआ है।
 ==एएम ==
-[[जटिलता वर्ग|कॉम्पलेक्सिटी वर्ग]] '''एएम''' (या '''एएम [2]''') [[निर्णय समस्या|निर्णय समस्याओं]] का समूह है जिसे दो संदेशों के साथ आर्थर-मर्लिन प्रोटोकॉल द्वारा बहुपद समय में निश्चित किया जा सकता है। केवल प्रश्न या प्रतिक्रिया युग्म है: आर्थर कुछ रैंडम सिक्के उछालता है और अपने सिक्के उछालने के सभी परिणामों का परिणाम मर्लिन को प्रदान करता है, मर्लिन कथित प्रूफ के साथ उत्तर देता है, और आर्थर निश्चित रूप से प्रूफ की पुष्टि करता है। इस प्रोटोकॉल में, आर्थर को केवल सिक्का उछालने के परिणाम मर्लिन को प्रदान करने की अनुमति है, और अंतिम चरण में आर्थर को केवल अपने पूर्व से उत्पन्न रैंडम सिक्का फ्लिप और मर्लिन के संदेश का उपयोग करके यह निर्णय लेना होगा कि उसे स्वीकार करना है या अस्वीकार करना है।
+[[जटिलता वर्ग|कॉम्पलेक्सिटी वर्ग]] '''एएम''' (या '''एएम [2]''') [[निर्णय समस्या|डिसिशन प्रॉब्लम्स]] का ग्रुप है जिसे दो संदेशों के साथ आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में निश्चित किया जा सकता है। केवल प्रश्न या प्रतिक्रिया युग्म है: आर्थर कुछ रैंडम सिक्के उछालता है और अपने सिक्के उछालने के सभी परिणामों का परिणाम मर्लिन को प्रदान करता है, मर्लिन कथित प्रूफ के साथ उत्तर देता है, और आर्थर निश्चित रूप से प्रूफ की पुष्टि करता है। इस प्रोटोकॉल में, आर्थर को केवल सिक्का उछालने के परिणाम मर्लिन को प्रदान करने की अनुमति है, और अंतिम चरण में आर्थर को केवल अपने पूर्व से उत्पन्न रैंडम सिक्का फ्लिप और मर्लिन के मैसेज का उपयोग करके यह डिसिशन लेना होगा कि उसे एक्सेप्ट करना है या अस्वीकार करना है।
-दूसरे शब्दों में, लैंग्वेज ''L'' एएम में है यदि बहुपद-समय नियतात्मक ट्यूरिंग मशीन ''M'' और बहुपद ''p'', ''q'' उपस्थित है जैसे कि प्रत्येक इनपुट स्ट्रिंग ''x'' लंबाई के लिए ''n'' = |''x''| है।
+दूसरे शब्दों में, लैंग्वेज ''L'' एएम में है यदि पोलीनोमिअल-टाइम नियतात्मक ट्यूरिंग मशीन ''M'' और पोलीनोमिअल ''p'', ''q'' उपस्थित है जैसे कि प्रत्येक इनपुट स्ट्रिंग ''x'' लंबाई के लिए ''n'' = |''x''| है।
 *यदि ''x'' ''L'' में है, तो <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\exists z\in\{0,1\}^{q(n)}\,M(x,y,z)=1)\ge2/3</math> प्राप्त होता है।
 *यदि x, L में नहीं है, तो <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\forall z\in\{0,1\}^{q(n)}\,M(x,y,z)=0)\ge2/3</math> प्राप्त होता है।
 यहां दूसरे नियम को इस प्रकार पुनः लिखा जा सकता है:
 *यदि x, L में नहीं है, तो <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\exists z\in\{0,1\}^{q(n)}\,M(x,y,z)=1)\le1/3</math> प्राप्त होता है।
-जैसा कि ऊपर दिया गया है, z मर्लिन का कथित प्रूफ है (जिसका आकार बहुपद से घिरा हुआ है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो बहुपद से भी घिरा हुआ है।
+जैसा कि ऊपर दिया गया है, z मर्लिन का कथित प्रूफ है (जिसका साइज पोलीनोमिअल से घिरा हुआ है) और y वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी घिरा हुआ है।
-कॉम्पलेक्सिटी वर्ग '''<nowiki/>'एएम[k]'<nowiki/>''' समस्याओं का समूह है जिसे k प्रश्नों और प्रतिक्रियाओं के साथ बहुपद समय में निश्चित किया जा सकता है। जैसा कि ऊपर परिभाषित है '''<nowiki/>'एएम'<nowiki/>''' '''<nowiki/>'एएम[2]'''' है। '''<nowiki/>'एएम[3]'''' का प्रारम्भ मर्लिन से आर्थर के लिए संदेश के साथ होगी, फिर आर्थर से मर्लिन के लिए संदेश और फिर अंत में मर्लिन से आर्थर के लिए संदेश के साथ होता है। अंतिम संदेश सदैव मर्लिन की ओर से आर्थर के लिए होना चाहिए, क्योंकि आर्थर के लिए अपना उत्तर निश्चित करने के पश्चात मर्लिन को संदेश प्रेक्षित करने से कभी सहायता नहीं मिलती है।
+कॉम्पलेक्सिटी वर्ग '''<nowiki/>'एएम[k]'<nowiki/>''' प्रॉब्लम्स का ग्रुप है जिसे k प्रश्नों और प्रतिक्रियाओं के साथ पोलीनोमिअल टाइम में निश्चित किया जा सकता है। जैसा कि ऊपर परिभाषित है '''<nowiki/>'एएम'<nowiki/>''' '''<nowiki/>'एएम[2]'<nowiki/>''' है। '''<nowiki/>'एएम[3]'''' का प्रारम्भ मर्लिन से आर्थर के लिए मैसेज के साथ होगी, फिर आर्थर से मर्लिन के लिए मैसेज और फिर अंत में मर्लिन से आर्थर के लिए मैसेज के साथ होता है। अंतिम मैसेज सदैव मर्लिन की ओर से आर्थर के लिए होना चाहिए, क्योंकि आर्थर के लिए अपना उत्तर निश्चित करने के पश्चात मर्लिन को मैसेज सेंड करने से कभी सहायता नहीं मिलती है।
 ==गुण==
@@ Line 30: / Line 30: @@
 [[File:Arthur-Merlin classes diagram.svg|alt=A diagram showcasing the relationships of MA and AM with other complexity classes described in the article.|अंगूठे|अन्य जटिलता वर्गों के साथ एमए और एएम के ज्ञात संबंध। वर्ग ''ए'' से वर्ग ''बी'' तक एक तीर का अर्थ है कि ''ए'' ''बी'' का उपसमुच्चय है।]]
-* '''एमए''' और '''एएम''' दोनों अपरिवर्तित रहते हैं यदि उनकी परिभाषाओं को पूर्ण पूर्णता की आवश्यकता के लिए परिवर्तित कर दिया जाता है, जिसका अर्थ है कि आर्थर संभावना 1 (2/3 के अतिरिक्त) को स्वीकार करता है जब x लैंग्वेज में होता है।<ref>For a proof, see {{cite web|url=http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf|title=Lecture 17: Arthur-Merlin games, Zero-knowledge proofs|author=Rafael Pass and Jean-Baptiste Jeannin|date=March 24, 2009|access-date=June 23, 2010}}</ref>
+* '''एमए''' और '''एएम''' दोनों अपरिवर्तित रहते हैं यदि उनकी परिभाषाओं को पूर्ण पूर्णता की आवश्यकता के लिए परिवर्तित कर दिया जाता है, जिसका अर्थ है कि आर्थर प्रोबेबिलिटी 1 (2/3 के अतिरिक्त) को एक्सेप्ट करता है जब x लैंग्वेज में होता है।<ref>For a proof, see {{cite web|url=http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf|title=Lecture 17: Arthur-Merlin games, Zero-knowledge proofs|author=Rafael Pass and Jean-Baptiste Jeannin|date=March 24, 2009|access-date=June 23, 2010}}</ref>
-* किसी भी स्थिरांक k ≥ 2 के लिए, वर्ग '''<nowiki/>'एएम[k]' 'एएम[2]'<nowiki/>''' के समान है। यदि k को इनपुट आकार से बहुपद रूप से संबंधित किया जा सकता है, तो वर्ग ''''एएम'''<nowiki/>'[poly(n)] वर्ग, '''आईपी''' के समान है, जिसे ''''[[PSPACE|पीस्पेस]]'''' के समान माना जाता है और व्यापक रूप से वर्ग '''<nowiki/>'एएम[2]'''' से अधिक स्थिर माना जाता है।
+* किसी भी स्थिरांक k ≥ 2 के लिए, वर्ग '''<nowiki/>'एएम[k]' 'एएम[2]'<nowiki/>''' के समान है। यदि k को इनपुट साइज से पोलीनोमिअल रूप से संबंधित किया जा सकता है, तो वर्ग<nowiki/> ''''एएम'''<nowiki>'[poly(n)] वर्ग, </nowiki>'''आईपी''' के समान है, जिसे ''''[[PSPACE|पीस्पेस]]'''' के समान माना जाता है और व्यापक रूप से '''<nowiki/>'''वर्ग '''<nowiki/>'एएम[2]'''' से अधिक स्थिर माना जाता है।
-* '''<nowiki/>'एएम'''' में '''<nowiki/>'एमए'''' निहित है, क्योंकि '''<nowiki/>'एएम''''[3] में '''<nowiki/>'एमए'''' सम्मिलित है: आर्थर, मर्लिन का प्रमाणपत्र प्राप्त करने के पश्चात, आवश्यक नंबर में सिक्के उछाल सकता है, उन्हें मर्लिन को प्रेक्षित कर सकता है, और प्रतिक्रिया को अनदेखा कर सकता है।
+* '''<nowiki/>'एएम'''' में '''<nowiki/>'एमए'''' निहित है, क्योंकि '''<nowiki/>'एएम''''[3] में '''<nowiki/>'एमए'''' सम्मिलित है: आर्थर, मर्लिन का प्रमाणपत्र प्राप्त करने के पश्चात, आवश्यक नंबर में सिक्के उछाल सकता है, उन्हें मर्लिन को सेंड कर सकता है, और प्रतिक्रिया को अनदेखा कर सकता है।
 * यह संवृत है कि क्या '''<nowiki/>'एएम'''' और '''<nowiki/>'एमए'''' भिन्न-भिन्न हैं। प्रशंसनीय सर्किट निचली सीमा के अनुसार ('''P'''='''BPP''' के समान), वे दोनों '''<nowiki/>'एनपी'''' के समान हैं।<ref>{{Cite book |last1=Impagliazzo |first1=Russell |last2=Wigderson |first2=Avi |date=1997-05-04 |title=P = BPP if E requires exponential circuits: derandomizing the XOR lemma |publisher=ACM |pages=220–229 |doi=10.1145/258533.258590 |isbn=0897918886|s2cid=18921599 }}</ref>
 * '''एएम''' वर्ग बीपी⋅एनपी के समान है जहां बीपी बाउंडेड-एरर प्रोबेबिलिस्टिक ऑपरेटर को प्रदर्शित करता है। <math> \exists \cdot \mathsf{BPP}</math>(जिसे एक्सिस्ट्सबीपीपी के रूप में भी लिखा जाता है) भी '''एमए''' का उपसमूह है। क्या '''एमए''' के समान है <math> \exists \cdot \mathsf{BPP}</math> संवृत प्रश्न है।
-* निजी सिक्का प्रोटोकॉल में रूपांतरण, जिसमें मर्लिन आर्थर के रैंडम निर्णयों के प्रणाम की भविष्यवाणी नहीं कर सकता है, सामान्य स्थिति में इंटरैक्शन के समय की नंबर अधिकतम 2 तक बढ़ा देता है। तो '''एएम''' का निजी-सिक्का संस्करण सार्वजनिक-सिक्का संस्करण के समान है।
+* निजी सिक्का प्रोटोकॉल में रूपांतरण, जिसमें मर्लिन आर्थर के रैंडम निर्णयों के प्रणाम की भविष्यवाणी नहीं कर सकता है, सामान्य स्थिति में इंटरैक्शन के टाइम की नंबर अधिकतम 2 तक बढ़ा देता है। तो '''एएम''' का निजी-सिक्का संस्करण सार्वजनिक-सिक्का संस्करण के समान है।
-* '''एमए''' में [[एनपी (जटिलता)|'''एनपी''']] और [[बीपीपी (जटिलता)|'''बीपीपी''']] दोनों सम्मिलित हैं। बीपीपी के लिए यह शीघ्र है, क्योंकि आर्थर मर्लिन को सरलता से त्याग सकता है और प्रॉब्लम का सीधे सॉल्व कर सकता है; '''एनपी''' के लिए, मर्लिन को केवल आर्थर को प्रमाणपत्र प्रदान करने की आवश्यकता है, जिसे आर्थर बहुपद समय में नियतात्मक रूप से मान्य कर सकता है।
+* '''एमए''' में [[एनपी (जटिलता)|'''एनपी''']] और [[बीपीपी (जटिलता)|'''बीपीपी''']] दोनों सम्मिलित हैं। बीपीपी के लिए यह शीघ्र है, क्योंकि आर्थर मर्लिन को सरलता से त्याग सकता है और प्रॉब्लम का सीधे सॉल्व कर सकता है; '''एनपी''' के लिए, मर्लिन को केवल आर्थर को प्रमाणपत्र प्रदान करने की आवश्यकता है, जिसे आर्थर पोलीनोमिअल टाइम में नियतात्मक रूप से मान्य कर सकता है।
-* '''एमए''' और '''एएम''' दोनों [[बहुपद पदानुक्रम]] में समाहित हैं। विशेष रूप से, '''एमए''' Σ<sub>2</sub><sup>P</sup> और Π<sub>2</sub><sup>P</sup> के प्रतिच्छेदन में निहित है और '''एएम''' Π<sub>2</sub><sup>P</sup> में निहित है। इससे भी अधिक, '''एमए''' उपवर्ग {{nowrap|S{{su|p=P|b=2}}}}<ref>{{cite web|url=http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf |title=सममित प्रत्यावर्तन BPP को कैप्चर करता है|website=Ccs.neu.edu|access-date=2016-07-26}}</ref> में समाहित है, कॉम्पलेक्सिटी वर्ग जो सममित प्रत्यावर्तन को व्यक्त करता है। यह सिप्सर-लॉटमैन प्रमेय का सामान्यीकरण है।
+* '''एमए''' और '''एएम''' दोनों [[बहुपद पदानुक्रम|पोलीनोमिअल पदानुक्रम]] में समाहित हैं। विशेष रूप से, '''एमए''' Σ<sub>2</sub><sup>P</sup> और Π<sub>2</sub><sup>P</sup> के प्रतिच्छेदन में निहित है और '''एएम''' Π<sub>2</sub><sup>P</sup> में निहित है। इससे भी अधिक, '''एमए''' उपवर्ग {{nowrap|S{{su|p=P|b=2}}}}<ref>{{cite web|url=http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf |title=सममित प्रत्यावर्तन BPP को कैप्चर करता है|website=Ccs.neu.edu|access-date=2016-07-26}}</ref> में समाहित है, कॉम्पलेक्सिटी वर्ग जो सममित प्रत्यावर्तन को व्यक्त करता है। यह सिप्सर-लॉटमैन प्रमेय का सामान्यीकरण है।
-* '''एएम''' '''एनपी'''/'''पॉली''' में समाहित है, जो बहुपद आकार [[सलाह (जटिलता)|सम्मति]] के साथ अन्य-नियतात्मक बहुपद समय में गणना योग्य निर्णय समस्याओं का वर्ग है। प्रूफ एडलमैन के प्रमेय का रूपांतर है।
+* '''एएम''' '''एनपी'''/'''पॉली''' में समाहित है, जो पोलीनोमिअल साइज [[सलाह (जटिलता)|सम्मति]] के साथ अन्य-नियतात्मक पोलीनोमिअल टाइम में कैलकुलेशन योग्य डिसिशन प्रॉब्लम्स का वर्ग है। प्रूफ एडलमैन के प्रमेय का रूपांतर है।
 * '''एमए''' [[पीपी (जटिलता)|'''पीपी''']] में निहित है; यह परिणाम वीरशैचिन के कारण है।<ref>{{Cite book|last=Vereschchagin|first=N.K. |pages=138–143 |doi=10.1109/sct.1992.215389|isbn=081862955X|year=1992|chapter=On the power of PP |title=&#91;1992&#93; Proceedings of the Seventh Annual Structure in Complexity Theory Conference |s2cid=195705029 }}</ref>
 * '''एमए''' इसके क्वांटम संस्करण, [[क्यूएमए|'''क्यूएमए''']] में निहित है।<ref>{{Cite journal |last1=Vidick |first1=Thomas |last2=Watrous |first2=John |date=2016 |title=क्वांटम प्रमाण|journal=Foundations and Trends in Theoretical Computer Science |volume=11 |issue=1–2 |pages=1–215 |doi=10.1561/0400000068 |issn=1551-305X|arxiv=1610.01664 |s2cid=54255188 }}</ref>
-* '''एएम''' में यह निर्णय लेने की [[ग्राफ समरूपता समस्या|प्रॉब्लम]] है कि क्या दो ग्राफ समरूपी नहीं हैं। निजी सिक्कों का उपयोग करने वाला प्रोटोकॉल निम्नलिखित है और इसे सार्वजनिक सिक्का प्रोटोकॉल में परिवर्तित किया जा सकता है। दो ग्राफ G और H दिए गए हैं, आर्थर रैंडम रूप से उनमें से एक का चयन करता है, और इसके शीर्षों का रैंडम क्रमचय चयनित करता है, क्रमबद्ध ग्राफ I को मर्लिन के सामने प्रस्तुत करता है। मर्लिन को उत्तर देना होगा कि क्या I G या H से बना है। यदि ग्राफ़ अन्य-समरूपी हैं, तो मर्लिन पूर्ण निश्चितता के साथ उत्तर देने में सक्षम होंगे (यह परीक्षण करके कि क्या I G के समरूपी है)। चूँकि , यदि ग्राफ समरूपी हैं, तो यह संभव है कि I बनाने के लिए G या H का उपयोग किया गया था, और यह समान रूप से संभव है। इस स्थिति में, मर्लिन के पास उन्हें भिन्न बताने की कोई विधि नहीं है और वह आर्थर को अधिकतम 1/2 संभावना के साथ मना सकता है, और इसे दोहराव द्वारा 1/4 तक बढ़ाया जा सकता है। यह वास्तव में [[शून्य ज्ञान प्रमाण|शून्य ज्ञान प्रूफ]] है।
+* '''एएम''' में यह डिसिशन लेने की [[ग्राफ समरूपता समस्या|प्रॉब्लम]] है कि क्या दो ग्राफ समरूपी नहीं हैं। निजी सिक्कों का उपयोग करने वाला प्रोटोकॉल निम्नलिखित है और इसे सार्वजनिक सिक्का प्रोटोकॉल में परिवर्तित किया जा सकता है। दो ग्राफ G और H दिए गए हैं, आर्थर रैंडम रूप से उनमें से एक का चयन करता है, और इसके शीर्षों का रैंडम क्रमचय चयनित करता है, क्रमबद्ध ग्राफ I को मर्लिन के सामने प्रस्तुत करता है। मर्लिन को उत्तर देना होगा कि क्या I G या H से बना है। यदि ग्राफ़ अन्य-समरूपी हैं, तो मर्लिन पूर्ण निश्चितता के साथ उत्तर देने में सक्षम होंगे (यह परीक्षण करके कि क्या I G के समरूपी है)। चूँकि , यदि ग्राफ समरूपी हैं, तो यह संभव है कि I बनाने के लिए G या H का उपयोग किया गया था, और यह समान रूप से संभव है। इस स्थिति में, मर्लिन के पास उन्हें भिन्न बताने की कोई विधि नहीं है और वह आर्थर को अधिकतम 1/2 प्रोबेबिलिटी के साथ मना सकता है, और इसे दोहराव द्वारा 1/4 तक बढ़ाया जा सकता है। यह वास्तव में [[शून्य ज्ञान प्रमाण|शून्य ज्ञान प्रूफ]] है।
-* यदि '''एएम''' में coNP है '''PH = AM''' है। यह इस विषय का प्रूफ है कि ग्राफ समरूपता एनपी-पूर्ण होने की संभावना नहीं है, क्योंकि इसका तात्पर्य बहुपद पदानुक्रम के पतन से है।
+* यदि '''एएम''' में coNP है '''PH = AM''' है। यह इस विषय का प्रूफ है कि ग्राफ समरूपता एनपी-पूर्ण होने की प्रोबेबिलिटी नहीं है, क्योंकि इसका तात्पर्य पोलीनोमिअल पदानुक्रम के पतन से है।
 * यह ज्ञात है, [[विस्तारित रीमैन परिकल्पना|ईआरएच]] मानते हुए, कि किसी भी d प्रॉब्लम के लिए बहुभिन्नरूपी बहुपदों का संग्रह दिया गया है <math>f_i</math> प्रत्येक पूर्णांक गुणांक और अधिकतम d डिग्री के साथ, क्या उनके निकट सामान्य सम्मिश्र शून्य है? 'एएम' में है।<ref>{{cite web|url=http://people.csail.mit.edu/madhu/FT98/course.html |title=Course: Algebra and Computation |website=People.csail.mit.edu |access-date=2016-07-26}}</ref>

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

आर्थर-मर्लिन प्रोटोकॉल: Difference between revisions

Namespaces

More

Page actions

Revision as of 19:24, 14 September 2023

Contents

एमए

एएम

गुण

संदर्भ

ग्रन्थसूची

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आर्थर-मर्लिन प्रोटोकॉल: Difference between revisions

Revision as of 19:24, 14 September 2023

एमए

एएम

गुण

संदर्भ

ग्रन्थसूची

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories