इंटरैक्टिव प्रमाण प्रणाली

Not to be confused with Proof assistant.

एक इंटरैक्टिव प्रूफ़ प्रोटोकॉल का सामान्य प्रतिनिधित्व।

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

सभी इंटरैक्टिव प्रूफ सिस्टम की दो आवश्यकताएँ होती हैं:

• पूर्णता: यदि कथन सत्य है, तो ईमानदार सत्यापनकर्ता (अर्थात प्रोटोकॉल का ठीक से पालन करने वाला) ईमानदार सत्यापनकर्ता को यह विश्वास दिला सकता है कि यह वास्तव में सत्य है।
• सुदृढ़ता: यदि कथन गलत है, तो कोई भी सूचक, भले ही वह प्रोटोकॉल का पालन न करता हो, ईमानदार सत्यापनकर्ता को यह विश्वास नहीं दिला सकता कि यह सत्य है, कुछ छोटी संभावनाओं को छोड़कर।

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

पृष्ठभूमि

प्रत्येक इंटरैक्टिव प्रूफ सिस्टम स्ट्रिंग्स की एक औपचारिक भाषा को परिभाषित करता है $L$. प्रमाण प्रणाली की सुदृढ़ता उस संपत्ति को संदर्भित करती है जिसे कोई भी नीति सत्यापनकर्ता गलत कथन के लिए स्वीकार नहीं कर सकता है $y\not \in L$ कुछ छोटी संभावनाओं को छोड़कर। इस संभावना की ऊपरी सीमा को प्रूफ सिस्टम की सुदृढ़ता त्रुटि के रूप में जाना जाता है। अधिक औपचारिक रूप से, प्रत्येक कहावत के लिए $({\tilde {\mathcal {P}}})$, और हर $y\not \in L$:

$\Pr[(\perp ,({\text{accept}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon .$

कुछ के लिए $\epsilon \ll 1$. जब तक सुदृढ़ता त्रुटि सत्यापनकर्ता के संभावित चलने के समय के बहुपद अंश से बंधी होती है (यानी) $\epsilon \leq 1/\mathrm {poly} (|y|)$), सुदृढ़ता को बढ़ाना हमेशा संभव होता है जब तक कि सत्यापनकर्ता के चलने के समय के सापेक्ष सुदृढ़ता त्रुटि नगण्य न हो जाए। यह प्रमाण को दोहराने और सभी प्रमाण सत्यापित होने पर ही स्वीकार करने से प्राप्त होता है। बाद $\ell$ दोहराव, एक ध्वनि त्रुटि $\epsilon$ तक कम कर दिया जाएगा $\epsilon ^{\ell }$.

इंटरैक्टिव प्रमाणों की श्रेणियां

एनपी

जटिलता वर्ग [[एनपी (जटिलता)]] को एक बहुत ही सरल प्रमाण प्रणाली के रूप में देखा जा सकता है। इस प्रणाली में, सत्यापनकर्ता एक नियतात्मक, बहुपद-समय मशीन (एक पी (जटिलता) मशीन) है। प्रोटोकॉल है:

• प्रोवर इनपुट को देखता है और अपनी असीमित शक्ति का उपयोग करके समाधान की गणना करता है और एक बहुपद-आकार प्रमाण प्रमाण पत्र लौटाता है।
• सत्यापनकर्ता सत्यापित करता है कि प्रमाणपत्र नियतात्मक बहुपद समय में वैध है। यदि यह वैध है, तो यह स्वीकार करता है; अन्यथा, यह अस्वीकार कर देता है।

ऐसे मामले में जहां एक वैध प्रमाण प्रमाणपत्र मौजूद है, सूचक हमेशा उस प्रमाणपत्र को देकर सत्यापनकर्ता को स्वीकार करने में सक्षम होता है। ऐसे मामले में जहां कोई वैध प्रमाण प्रमाणपत्र नहीं है, हालांकि, इनपुट भाषा में नहीं है, और कोई भी सूचक, चाहे वह कितना भी दुर्भावनापूर्ण हो, सत्यापनकर्ता को अन्यथा मना नहीं सकता है, क्योंकि किसी भी प्रमाण प्रमाणपत्र को अस्वीकार कर दिया जाएगा।

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

Main article: Arthur–Merlin protocol

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

विशेष रूप से वर्ग 'एमए' उपरोक्त एनपी इंटरैक्शन का एक सरल सामान्यीकरण है जिसमें सत्यापनकर्ता नियतात्मक के बजाय संभाव्य है। साथ ही, यह अपेक्षा करने के बजाय कि सत्यापनकर्ता हमेशा वैध प्रमाणपत्र स्वीकार करें और अमान्य प्रमाणपत्र अस्वीकार करें, यह अधिक उदार है:

• 'पूर्णता:' यदि स्ट्रिंग भाषा में है, तो सूचक को एक प्रमाण पत्र देने में सक्षम होना चाहिए, जिसे सत्यापनकर्ता कम से कम 2/3 संभावना के साथ स्वीकार करेगा (सत्यापनकर्ता के यादृच्छिक विकल्पों के आधार पर)।
• 'सुदृढ़ता:' यदि स्ट्रिंग भाषा में नहीं है, तो कोई भी कहावत, चाहे वह कितनी भी दुर्भावनापूर्ण क्यों न हो, सत्यापनकर्ता को 1/3 से अधिक संभावना वाली स्ट्रिंग को स्वीकार करने के लिए मनाने में सक्षम नहीं होगी।

यह मशीन सामान्य एनपी इंटरेक्शन प्रोटोकॉल की तुलना में संभावित रूप से अधिक शक्तिशाली है, और प्रमाणपत्र सत्यापित करने के लिए कम व्यावहारिक नहीं हैं, क्योंकि 'बीपीपी' एल्गोरिदम को अमूर्त व्यावहारिक गणना के रूप में माना जाता है (परिबद्ध-त्रुटि संभाव्य बहुपद देखें)।

सार्वजनिक सिक्का प्रोटोकॉल बनाम निजी सिक्का प्रोटोकॉल

सार्वजनिक सिक्का प्रोटोकॉल में, सत्यापनकर्ता द्वारा चुने गए यादृच्छिक विकल्पों को सार्वजनिक किया जाता है। वे निजी सिक्का प्रोटोकॉल में निजी रहते हैं।

उसी सम्मेलन में जहां बाबई ने 'एमए' के ​​लिए अपनी प्रमाण प्रणाली को परिभाषित किया, शफ़ी गोल्डवेसर, सिल्वियो मिकाली और चार्ल्स रैकॉफ़ इंटरैक्टिव प्रूफ सिस्टम आईपी[एफ(एन)] को परिभाषित करने वाला एक पेपर प्रकाशित किया। इसमें एमए प्रोटोकॉल के समान मशीनें हैं, सिवाय इसके कि एन आकार के इनपुट के लिए एफ(एन) राउंड की अनुमति है। प्रत्येक दौर में, सत्यापनकर्ता गणना करता है और प्रूवर को एक संदेश भेजता है, और प्रूवर गणना करता है और सत्यापनकर्ता को जानकारी वापस भेजता है। अंत में सत्यापनकर्ता को अपना निर्णय लेना होगा। उदाहरण के लिए, एक आईपी[3] प्रोटोकॉल में, अनुक्रम वीपीवीपीवीपीवी होगा, जहां वी एक सत्यापनकर्ता टर्न है और पी एक प्रोवर टर्न है।

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

सार्वजनिक सिक्कों के साथ मुख्य समस्या यह है कि यदि सूचक दुर्भावनापूर्वक सत्यापनकर्ता को एक स्ट्रिंग स्वीकार करने के लिए राजी करना चाहता है जो भाषा में नहीं है, तो ऐसा लगता है कि सत्यापनकर्ता अपनी योजनाओं को विफल करने में सक्षम हो सकता है यदि वह अपनी आंतरिक स्थिति को इससे छिपा सकता है। आईपी ​​प्रूफ सिस्टम को परिभाषित करने में यह एक प्राथमिक प्रेरणा थी।

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

आईपी

Main article: IP (complexity)

निजी सिक्के मददगार नहीं हो सकते हैं, लेकिन बातचीत के अधिक दौर मददगार होते हैं। यदि हम संभाव्य सत्यापनकर्ता मशीन और सर्व-शक्तिशाली प्रोवर को बहुपद संख्या में राउंड के लिए बातचीत करने की अनुमति देते हैं, तो हमें समस्याओं का वर्ग मिलता है जिसे आईपी कहा जाता है। 1992 में, आदि शमीर ने जटिलता सिद्धांत के केंद्रीय परिणामों में से एक में खुलासा किया कि आईपी PSPACE के बराबर है, बहुपद अंतरिक्ष में एक साधारण नियतात्मक ट्यूरिंग मशीन द्वारा हल की जाने वाली समस्याओं का वर्ग।

क्यूआईपी

Main article: QIP (complexity)

यदि हम सिस्टम के तत्वों को क्वांटम गणना का उपयोग करने की अनुमति देते हैं, तो सिस्टम को क्वांटम इंटरैक्टिव प्रूफ सिस्टम कहा जाता है, और संबंधित जटिलता वर्ग को क्यूआईपी कहा जाता है। परिणामों की एक श्रृंखला 2010 में QIP = PSPACE की सफलता में परिणत हुई।

शून्य ज्ञान

Main article: Zero-knowledge proof

न केवल इंटरैक्टिव प्रूफ सिस्टम उन समस्याओं को हल कर सकते हैं जिन पर एनपी में विश्वास नहीं किया जाता है, बल्कि एक-तरफ़ा कार्यों के अस्तित्व के बारे में धारणाओं के तहत, एक प्रोवर सत्यापनकर्ता को समाधान के बारे में जानकारी दिए बिना समाधान के बारे में आश्वस्त कर सकता है। यह तब महत्वपूर्ण है जब सत्यापनकर्ता पर पूर्ण समाधान पर भरोसा नहीं किया जा सकता है। पहले तो यह असंभव लगता है कि सत्यापनकर्ता आश्वस्त हो सके कि कोई समाधान है जब सत्यापनकर्ता ने प्रमाणपत्र नहीं देखा है, लेकिन ऐसे प्रमाण, जिन्हें शून्य-ज्ञान प्रमाण के रूप में जाना जाता है, वास्तव में एनपी में सभी समस्याओं के लिए मौजूद माने जाते हैं और मूल्यवान हैं क्रिप्टोग्राफी. विशिष्ट संख्या सैद्धांतिक भाषाओं के लिए गोल्डवेसर, मिकाली और रैकॉफ द्वारा आईपी पर मूल 1985 पेपर में शून्य-ज्ञान प्रमाणों का पहली बार उल्लेख किया गया था। हालाँकि उनकी शक्ति की सीमा ओडेड गोल्डरेइच, सिल्वियो मिकाली और एवी विग्डर्सन द्वारा दिखाई गई थी।संपूर्ण एनपी के लिए, और इसे सबसे पहले रसेल इम्पाग्लिआज़ो और मोती युंग द्वारा सभी आईपी तक विस्तारित किया गया था।

एमआईपी

आईपी ​​के डिजाइनरों का एक लक्ष्य सबसे शक्तिशाली संभव इंटरैक्टिव प्रूफ सिस्टम बनाना था, और पहली नज़र में ऐसा लगता है कि सत्यापनकर्ता को अधिक शक्तिशाली और इतना अव्यवहारिक बनाए बिना इसे और अधिक शक्तिशाली नहीं बनाया जा सकता है। गोल्डवेसर एट अल. अपने 1988 के मल्टी प्रोवर इंटरैक्टिव प्रूफ़्स में इस पर काबू पा लिया: अट्रैक्टिविटी धारणाओं को कैसे दूर करें, जो एमआईपी नामक आईपी के एक प्रकार को परिभाषित करता है जिसमें दो स्वतंत्र प्रोवर्स होते हैं। एक बार जब सत्यापनकर्ता ने उन्हें संदेश भेजना शुरू कर दिया तो दोनों नीतियाँ संवाद नहीं कर सकतीं। जैसे यह बताना आसान है कि अपराधी झूठ बोल रहा है या नहीं, यदि उससे और उसके साथी से अलग-अलग कमरों में पूछताछ की जाती है, तो एक दुर्भावनापूर्ण सूचक का पता लगाना काफी आसान है जो सत्यापनकर्ता को एक स्ट्रिंग को स्वीकार करने के लिए धोखा देने की कोशिश कर रहा है जो भाषा में नहीं है यदि कोई अन्य सूचक है तो यह हो सकता है के साथ दोबारा जांच करें।

वास्तव में, यह इतना मददगार है कि बाबई, फ़ोर्टनो, और लुंड यह दिखाने में सक्षम थे कि एमआईपी = अगली बार, सभी समस्याओं का वर्ग जो घातीय समय में एक गैर-नियतात्मक ट्यूरिंग मशीन मशीन द्वारा हल किया जा सकता है, एक बहुत बड़ा वर्ग। NEXPTIME में PSPACE शामिल है, और माना जाता है कि इसमें पूरी तरह से PSPACE शामिल है। दो से अधिक अतिरिक्त सूक्तियों की निरंतर संख्या जोड़ने से किसी और भाषा की पहचान संभव नहीं हो पाती है। इस परिणाम ने प्रसिद्ध पीसीपी प्रमेय के लिए मार्ग प्रशस्त किया, जिसे इस प्रमेय का एक छोटा संस्करण माना जा सकता है।

एमआईपी में यह सहायक संपत्ति भी है कि एनपी में प्रत्येक भाषा के लिए शून्य-ज्ञान प्रमाण को आईपी द्वारा किए जाने वाले एकतरफा कार्यों की धारणा के बिना वर्णित किया जा सकता है। इसका असर संभवतः अटूट क्रिप्टोग्राफ़िक एल्गोरिदम के डिज़ाइन पर पड़ता है।इसके अलावा, एक एमआईपी प्रोटोकॉल केवल निरंतर संख्या में राउंड में आईपी में सभी भाषाओं को पहचान सकता है, और यदि कोई तीसरा प्रोवर जोड़ा जाता है, तो यह NEXPTIME में सभी भाषाओं को निरंतर संख्या में राउंड में पहचान सकता है, जिससे आईपी पर फिर से अपनी शक्ति दिखाई देती है।

यह ज्ञात है कि किसी भी स्थिरांक k के लिए, k प्रोवर्स और बहुपद रूप से कई राउंड वाली एक एमआईपी प्रणाली को केवल 2 प्रोवर्स और निरंतर संख्या में राउंड के साथ एक समतुल्य प्रणाली में बदला जा सकता है।

पीसीपी

Main article: Probabilistically checkable proof

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

विभिन्न पीसीपी कक्षाओं के बारे में आसानी से साबित होने वाले कई परिणाम हैं। ${\mathsf {PCP}}(0,{\mathsf {poly}})$, बहुपद-समय मशीनों का वर्ग जिसमें कोई यादृच्छिकता नहीं है लेकिन प्रमाणपत्र तक पहुंच है, सिर्फ एनपी है। ${\mathsf {PCP}}({\mathsf {poly}},0)$, बहुपद रूप से कई यादृच्छिक बिट्स तक पहुंच वाली बहुपद-समय मशीनों का वर्ग सह-आरपी (जटिलता) है। अरोरा और सफरा का पहला बड़ा परिणाम यही था PCP(log, log) = NP; दूसरे शब्दों में कहें तो, यदि एनपी प्रोटोकॉल में सत्यापनकर्ता केवल चुनने के लिए बाध्य है $O(\log n)$ प्रमाण प्रमाणपत्र के अंशों को देखने के लिए, इससे तब तक कोई फर्क नहीं पड़ेगा जब तक यह मौजूद है $O(\log n)$ उपयोग करने के लिए यादृच्छिक बिट्स। इसके अलावा, पीसीपी प्रमेय का दावा है कि प्रमाण पहुंच की संख्या को सभी तरह से एक स्थिरांक तक लाया जा सकता है। वह है, ${\mathsf {NP}}={\mathsf {PCP}}({\mathsf {log}},O(1))$. उन्होंने एनपी के इस मूल्यवान लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कुछ एनपी-पूर्ण समस्याओं के अनुकूलन संस्करणों के लिए सन्निकटन एल्गोरिदम मौजूद नहीं हैं जब तक कि पी = एनपी न हो। ऐसी समस्याओं का अध्ययन अब सन्निकटन की कठोरता नामक क्षेत्र में किया जाता है।

यह भी देखें

• ओरेकल मशीन
• ज्ञान का प्रमाण

पाठ्यपुस्तकें

• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, March 2009.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 10.4: Interactive Proof Systems, pp. 354–366.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Section 19.2: Games against nature and interactive protocols, pp. 469–480.

बाहरी संबंध

• Dexter Kozen. Interactive Proofs. CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
• Complexity Zoo:
  • MA, MA', MAEXP, MAE
  • AM, AMEXP, AM intersect co-AM, AM[polylog], coAM, BP•NP
  • QMA, QMA+, QMA(2), QMA_log, QMAM
  • IP, MIP, IPP, QIP, QIP(2), compIP, frIP
  • PCP(r(n),q(n))
• Larry Gonick. "Proof Positive?". A comic strip about interactive proof systems.