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

From Vigyanwiki
No edit summary
 
(4 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> प्राप्त होता है।
Line 14: Line 14:
उपरोक्त अनौपचारिक परिभाषा के साथ इसकी अपेक्षा करने के लिए, 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 वह रैंडम स्ट्रिंग है जिसका उपयोग आर्थर करता है, जो पोलीनोमिअल से भी बॉण्डेड है।


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