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

From Vigyanwiki
No edit summary
 
(11 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{short description|Interactive proof system in computational complexity theory}}
{{short description|Interactive proof system in computational complexity theory}}
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टिता सिद्धांत]] में, {{Harvtxt|बाबई |1985}}, द्वारा प्रस्तुत किया गया '''आर्थर-मर्लिन प्रोटोकॉल''', ऐसा [[इंटरैक्टिव प्रमाण प्रणाली|इंटरैक्टिव प्रमाण सिस्टम]] है जिसमें सत्यापनकर्ता के सिक्के उछालने को सार्वजनिक करने के लिए बाध्य किया जाता है (अर्थात नीतिकर्ता को भी इसकी सूचना होती है)। {{Harvtxt|गोल्डवेसर |सिप्सर |1986}} ने प्रमाणित किया कि निजी सिक्कों के साथ इच्छानुसार लंबाई के इंटरैक्टिव प्रमाण वाली सभी (औपचारिक) [[औपचारिक भाषा|लैंग्वेजेज]] में सार्वजनिक सिक्कों के साथ भी इंटरैक्टिव प्रमाण होते हैं।
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी]] में, {{Harvtxt|बाबई |1985}}, द्वारा प्रस्तुत किया गया '''आर्थर-मर्लिन प्रोटोकॉल''', ऐसा [[इंटरैक्टिव प्रमाण प्रणाली|इंटरैक्टिव प्रूफ सिस्टम]] है जिसमें वेरिफायर के कॉइन टोसेस को पब्लिक करने के लिए कन्स्ट्रैनड किया जाता है (अर्थात इसकी इनफार्मेशन होती है)। {{Harvtxt|गोल्डवेसर |सिप्सर |1986}} ने वेरीफाई किया कि प्राइवेट कॉइन के साथ इच्छानुसार लंबाई के इंटरैक्टिव प्रूफ वाली सभी (फॉर्मेट) [[औपचारिक भाषा|लैंग्वेजेज]] में पब्लिक कॉइन के साथ भी इंटरैक्टिव प्रूफ होते हैं।


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


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


औपचारिक रूप से, समष्टिता वर्ग '''<nowiki/>'एमए'<nowiki/>''' निर्णय समस्याओं का समूह है जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा बहुपद समय में निश्चित किया जा सकता है जहां मर्लिन का एकमात्र कदम आर्थर द्वारा किसी भी गणना से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L '''<nowiki/>'एमए'''' में है यदि बहुपद-समय नियतात्मक ट्यूरिंग मशीन M और बहुपद p, q उपस्थित है जैसे कि लंबाई के प्रत्येक इनपुट स्ट्रिंग x के लिए n = |x| है।
फॉर्मेट रूप से, कॉम्पलेक्सिटी क्लास '''<nowiki/>'MA '<nowiki/>''' डिसिशन प्रॉब्लम्स का ग्रुप है, जिसे आर्थर-मर्लिन प्रोटोकॉल द्वारा पोलीनोमिअल टाइम में कन्फर्म किया जा सकता है जहां मर्लिन का एकमात्र उपाय आर्थर द्वारा किसी भी कैलकुलेशन से पूर्व होता है। दूसरे शब्दों में, लैंग्वेज L '''<nowiki/>'MA '''' में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन 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>\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)=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> प्राप्त होता है।
*यदि 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 वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड हुआ है।


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


दूसरे शब्दों में, लैंग्वेज ''L'' एएम में है यदि बहुपद-समय नियतात्मक ट्यूरिंग मशीन ''M'' और बहुपद ''p'', ''q'' उपस्थित है जैसे कि प्रत्येक इनपुट स्ट्रिंग ''x'' लंबाई के लिए ''n'' = |''x''| है।
दूसरे शब्दों में, लैंग्वेज ''L'' AM में है यदि पोलीनोमिअल-टाइम डेटर्मीनिस्टिक ट्यूरिंग मशीन ''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)}}(\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)}}(\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> प्राप्त होता है।
*यदि 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 वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड है।


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


== संदर्भ ==
== संदर्भ ==
Line 74: Line 74:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:13, 2 February 2024

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

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

MA

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

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

  • यदि x, L में है, तो प्राप्त होता है।
  • यदि x, L में नहीं है, तो प्राप्त होता है।

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

  • यदि x, L में नहीं है, तो प्राप्त होता है।

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

AM

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

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

  • यदि x L में है, तो प्राप्त होता है।
  • यदि x, L में नहीं है, तो प्राप्त होता है।

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

  • यदि x, L में नहीं है, तो प्राप्त होता है।

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

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

गुण

A diagram showcasing the relationships of MA and AM with other complexity classes described in the article.

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

संदर्भ

  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.

ग्रन्थसूची

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=आर्थर-मर्लिन_प्रोटोकॉल&oldid=280991’