यादृच्छिक और संवादात्मक संगणना

एल्गोरिदम को सिक्के उछालने या एक शक्तिशाली लेकिन अविश्वसनीय प्रमाणक के साथ संवाद करने की अनुमति देने से BPP और IP जैसी जटिलता वर्ग उत्पन्न होते हैं जो कुशल सत्यापन क्या हासिल कर सकता है, इसकी हमारी समझ को नया आकार देते हैं।

Definition

यादृच्छिक संगणना एक मशीन को यादृच्छिक बिट्स तक पहुँच प्रदान करती है और एक सही उत्तर की संभावना को मापती है, जबकि संवादात्मक संगणना एक बहुपद-समय सत्यापनकर्ता को एक प्रमाणक के साथ संदेशों का आदान-प्रदान करने देती है; परिणामी वर्ग उन समस्याओं को पकड़ते हैं जिन्हें सीमित त्रुटि के साथ हल किया जा सकता है या बातचीत के माध्यम से सत्यापित किया जा सकता है।

Scope

यह विषय संभाव्य जटिलता वर्गों को शामिल करता है, जिनमें BPP, RP, और ZPP शामिल हैं, और यह प्रश्न कि क्या यादृच्छिकता को समाप्त किया जा सकता है, संवादात्मक प्रमाण प्रणालियाँ और IP को PSPACE के साथ पहचानने वाला प्रमेय, शून्य-ज्ञान प्रमाण, और संभाव्य रूप से जाँचने योग्य प्रमाण जो सन्निकटन की कठोरता को रेखांकित करते हैं।

Core questions

• क्या यादृच्छिकता तक पहुँच एल्गोरिदम को अधिक समस्याओं को कुशलता से हल करने देती है?
• क्या एक सीमित सत्यापनकर्ता एक अविश्वसनीय, शक्तिशाली प्रमाणक द्वारा किए गए दावों की जाँच कर सकता है?
• कोई व्यक्ति यह कैसे आश्वस्त हो सकता है कि एक कथन सत्य है जबकि कुछ और नहीं सीख रहा है?
• संवादात्मक और संभाव्य प्रमाण जाँच सन्निकटन को कैसे बाधित करती है?

Key theories

IP PSPACE के बराबर है

एक बहुपद-समय सत्यापनकर्ता और एक सर्व-शक्तिशाली प्रमाणक के बीच एक संवादात्मक प्रोटोकॉल द्वारा सिद्ध की जा सकने वाली भाषाएँ ठीक वही हैं जो बहुपद स्थान में निर्णय योग्य हैं, जो बातचीत की शक्ति का एक उल्लेखनीय माप है।

PCP प्रमेय

NP में प्रत्येक समस्या के ऐसे प्रमाण होते हैं जिन्हें यादृच्छिक रूप से चुने गए बिट्स की केवल एक स्थिर संख्या को पढ़कर सत्यापित किया जा सकता है, एक परिणाम जो सटीक सीमा को निर्धारित करता है जिसके आगे कई अनुकूलन समस्याओं का सन्निकटन NP-कठिन है।

Clinical relevance

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

History

संवादात्मक और शून्य-ज्ञान प्रमाण गोल्डवासर, मिकाली और रैकोफ द्वारा और बाबई द्वारा 1980 के दशक के मध्य में प्रस्तुत किए गए थे। शमीर ने 1990 में IP PSPACE के बराबर साबित किया, और PCP प्रमेय, जिसे 1990 के दशक की शुरुआत में अरोड़ा और अन्य द्वारा पूरा किया गया था, ने सन्निकटन के अध्ययन में क्रांति ला दी, जबकि यह स्थायी अनुमान कि यादृच्छिक बहुपद समय नियतात्मक बहुपद समय के बराबर है, अभी भी खुला है।

Debates

क्या यादृच्छिकता वास्तविक संगणनात्मक शक्ति जोड़ती है?

कई परिणाम बताते हैं कि प्रशंसनीय कठोरता धारणाओं के तहत BPP P के बराबर है, जिसका अर्थ है कि यादृच्छिकता को सैद्धांतिक रूप से कुशल एल्गोरिदम से हटाया जा सकता है। क्या यह व्युत्पन्नकरण बिना शर्त के रहता है, यह अनसुलझा है, यह खुला छोड़ रहा है कि यादृच्छिकता वास्तव में कितनी आवश्यक है।

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

सिक्के उछालना एक एल्गोरिथम की मदद कैसे कर सकता है?

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

शून्य-ज्ञान प्रमाण क्या है?

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