ZPP (जटिलता)

अन्य संभाव्य जटिलता वर्गों (आरपी ​​(जटिलता), सह-आरपी, बी पीपी (जटिलता), बीक्यूपी, पीपी (जटिलता)) के संबंध में जेडपीपी, जो पीएसपीएसीई के भीतर पी (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध सख्त है या नहीं।कम्प्यूटेशनल जटिलता सिद्धांत में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का जटिलता वर्ग है जिसके लिए इन गुणों के साथ संभाव्य ट्यूरिंग मशीन मौजूद है:

• यह हमेशा हां या ना में सही उत्तर देता है।
• प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद है।

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

वैकल्पिक रूप से, ZPP को उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके लिए इन गुणों के साथ संभाव्य ट्यूरिंग मशीन मौजूद है:

• यह सदैव बहुपद समय में चलता है।
• इसका उत्तर हां, नहीं या पता नहीं है।
• उत्तर हमेशा या तो पता नहीं या सही उत्तर होता है।
• यह प्रत्येक इनपुट के लिए अधिकतम 1/2 संभावना (और अन्यथा सही उत्तर) के साथ DO NOT KNOW लौटाता है।

दोनों परिभाषाएँ समतुल्य हैं।

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

प्रतिच्छेदन परिभाषा

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

• मान लीजिए कि हमारे पास भाषा एल है जिसे आरपी एल्गोरिदम ए और (संभवतः पूरी तरह से अलग) सह-आरपी एल्गोरिदम बी दोनों द्वारा मान्यता प्राप्त है।
• किसी इनपुट को देखते हुए, चरण के लिए इनपुट पर A चलाएँ। यदि यह हाँ लौटाता है, तो उत्तर हाँ होना चाहिए। अन्यथा, चरण के लिए इनपुट पर B चलाएँ। यदि यह 'नहीं' लौटाता है, तो उत्तर 'नहीं' होना चाहिए। यदि ऐसा कुछ नहीं होता है, तो इस चरण को दोहराएँ।

ध्यान दें कि केवल मशीन ही गलत उत्तर दे सकती है, और प्रत्येक पुनरावृत्ति के दौरान उस मशीन के गलत उत्तर देने की संभावना अधिकतम 50% है। इसका मतलब यह है कि kवें दौर तक पहुंचने की संभावना k में तेजी से घट जाती है, जिससे पता चलता है कि अपेक्षित मूल्य चलने का समय बहुपद है। इससे पता चलता है कि आरपी इंटरसेक्ट सह-आरपी जेडपीपी में समाहित है।

यह दिखाने के लिए कि ZPP आरपी इंटरसेक्ट सह-आरपी में समाहित है, मान लीजिए कि हमारे पास समस्या को हल करने के लिए लास वेगास एल्गोरिदम सी है। फिर हम निम्नलिखित आरपी एल्गोरिदम का निर्माण कर सकते हैं:

• C को उसके अपेक्षित रनिंग समय से कम से कम दोगुने तक चलाएँ। यदि यह कोई उत्तर देता है तो वह उत्तर दीजिए। यदि यह हमारे रोकने से पहले कोई उत्तर नहीं देता है, तो 'नहीं' दें।

मार्कोव की असमानता|मार्कोव की असमानता से, हमारे रोकने से पहले इसका उत्तर मिलने की संभावना कम से कम 1/2 है। इसका मतलब यह है कि हाँ उदाहरण पर हम रुककर और 'नहीं' देकर गलत उत्तर देंगे, यह मौका अधिकतम 1/2 है, जो आरपी एल्गोरिथ्म की परिभाषा के अनुरूप है। सह-आरपी एल्गोरिथ्म समान है, सिवाय इसके कि यदि C का समय समाप्त हो जाता है तो यह हाँ देता है।

साक्षी और प्रमाण

एनपी, आरपी और जेडपीपी वर्गों को सेट में सदस्यता के प्रमाण के संदर्भ में सोचा जा सकता है।

परिभाषा: सेट एक्स के लिए सत्यापनकर्ता वी ट्यूरिंग मशीन है जैसे:

• यदि x X में है तो स्ट्रिंग w मौजूद है जैसे कि V(x,w) स्वीकार करता है;
• यदि x X में नहीं है, तो सभी स्ट्रिंग्स के लिए w, V(x,w) अस्वीकार कर देता है।

स्ट्रिंग w को सदस्यता का प्रमाण माना जा सकता है। लघु प्रमाणों के मामले में (इनपुट के आकार में बहुपद से घिरी लंबाई की) जिसे कुशलता से सत्यापित किया जा सकता है (V बहुपद-समय नियतात्मक ट्यूरिंग मशीन है), स्ट्रिंग w कहलाती है गवाह।

टिप्पणियाँ:

• परिभाषा बहुत असममित है. x के X में होने का प्रमाण एकल स्ट्रिंग है। एक्स के एक्स में न होने का प्रमाण सभी स्ट्रिंग्स का संग्रह है, जिनमें से कोई भी सदस्यता का प्रमाण नहीं है।
• एक्स में सभी एक्स के लिए एक्स में इसकी सदस्यता का गवाह होना चाहिए।
• गवाह को पारंपरिक रूप से समझा जाने वाला सबूत होना ज़रूरी नहीं है। यदि V संभाव्य ट्यूरिंग मशीन है जो संभवतः x को स्वीकार कर सकती है यदि x, किसी गैर-सदस्य को कभी स्वीकार नहीं करता)।
• सह-अवधारणा पूरक सेट में गैर-सदस्यता, या सदस्यता का प्रमाण है।

एनपी, आरपी और जेडपीपी वर्ग ऐसे सेट हैं जिनकी सदस्यता के लिए गवाह हैं। वर्ग एनपी के लिए केवल यह आवश्यक है कि गवाह मौजूद हों। वे बहुत दुर्लभ हो सकते हैं. 2 में से^f(|x|)संभावित स्ट्रिंग, f बहुपद के साथ, सत्यापनकर्ता को स्वीकार करने के लिए केवल स्ट्रिंग की आवश्यकता होती है (यदि x,

'आरपी' और 'जेडपीपी' वर्गों के लिए यादृच्छिक रूप से चुनी गई कोई भी स्ट्रिंग संभवतः गवाह होगी।

संबंधित सह-वर्गों में गैर-सदस्यता का प्रमाण है। विशेष रूप से, 'सह-आरपी' सेट का वह वर्ग है, जिसके लिए यदि x, X में नहीं है, तो कोई भी यादृच्छिक रूप से चुनी गई स्ट्रिंग गैर-सदस्यता का गवाह होने की संभावना है। 'जेडपीपी' सेटों का वह वर्ग है जिसके लिए कोई भी यादृच्छिक स्ट्रिंग एक्स में एक्स का गवाह होने की संभावना है, या एक्स में एक्स नहीं, जो भी मामला हो।

इस परिभाषा को 'आरपी', 'सह-आरपी' और 'जेडपीपी' की अन्य परिभाषाओं से जोड़ना आसान है। संभाव्य बहुपद-समय ट्यूरिंग मशीन V*_w(x) V* के यादृच्छिक टेप को V के लिए दूसरे इनपुट टेप से प्रतिस्थापित करके नियतात्मक बहुपद-समय ट्यूरिंग मशीन V(x, w) से मेल खाता है, जिस पर सिक्के के पलटने का क्रम लिखा होता है। गवाह को यादृच्छिक स्ट्रिंग के रूप में चुनकर, सत्यापनकर्ता संभाव्य बहुपद-समय ट्यूरिंग मशीन है जिसकी एक्स को स्वीकार करने की संभावना तब होती है जब एक्स एक्स में होता है (मान लीजिए 1/2 से अधिक), लेकिन शून्य यदि एक्स ∉ एक्स (के लिए) आरपी'); जब x, X में नहीं है तो x को अस्वीकार करने का मान बड़ा है लेकिन यदि x ∈ X ('co-RP' के लिए) है तो शून्य है; और एक्स के सदस्य के रूप में एक्स को सही ढंग से स्वीकार करने या अस्वीकार करने का बड़ा हिस्सा है, लेकिन एक्स को गलत तरीके से स्वीकार करने या अस्वीकार करने का शून्य है ('जेडपीपी' के लिए)।

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

'जेडपीपी' की तुलना 'बीपीपी' से की जानी चाहिए। वर्ग 'बीपीपी' को गवाहों की आवश्यकता नहीं है, हालांकि गवाह पर्याप्त हैं (इसलिए 'बीपीपी' में 'आरपी', 'सह-आरपी' और 'जेडपीपी' शामिल हैं)। 'बीपीपी' भाषा में V(x,w) अधिकांश स्ट्रिंग्स w पर स्वीकार होता है यदि x, इन्हें निश्चित होना आवश्यक है, और इसलिए इन्हें आम तौर पर सबूत या गवाह नहीं माना जा सकता।

जटिलता-सैद्धांतिक गुण

यह ज्ञात है कि ZPP पूरक के तहत बंद है; अर्थात्, ZPP = सह-ZPP।

ZPP अपने आप में कम (जटिलता) है, जिसका अर्थ है कि ZPP समस्याओं को तुरंत हल करने की शक्ति वाली ZPP मशीन (ZPP ऑरेकल मशीन) इस अतिरिक्त शक्ति के बिना मशीन से अधिक शक्तिशाली नहीं है। प्रतीकों में, ZPP^ZPP = ZPP.

ZPP^{उदाहरण के लिए:BPP} = ZPP^एनपी.

एनपी^BPPZPP में समाहित है^एनपी.

अन्य वर्गों से संबंध

चूँकि ZPP = RP ∩ coRP, ZPP स्पष्ट रूप से RP और coRP दोनों में समाहित है।

वर्ग P (जटिलता) ZPP में समाहित है, और कुछ कंप्यूटर वैज्ञानिकों ने अनुमान लगाया है कि P = ZPP, यानी, प्रत्येक लास वेगास एल्गोरिदम में नियतात्मक बहुपद-समय समतुल्य होता है।

वहाँ दैवज्ञ मौजूद है जिसके सापेक्ष ZPP = EXPTIME है। ZPP = EXPTIME के ​​लिए प्रमाण का अर्थ यह होगा कि P ≠ ZPP, जैसा कि P ≠ EXPTIME (समय पदानुक्रम प्रमेय देखें)।

यह भी देखें

• बीपीपी (जटिलता)
• आरपी (जटिलता)

बाहरी संबंध

• Complexity Zoo: ZPP Class ZPP