ZPP (जटिलता)

अन्य संभाव्य जटिलता वर्गों RP, co-RP, BPP, BQP, PP), (जटिलता) के संबंध में ZPP , जो PSPACE के अंदर P (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध कठोर है या नहीं।

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

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

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

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

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

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

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

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

वर्ग ZPP, वर्ग RP और co-RP के प्रतिच्छेदन के पूर्ण रूप से समान होते है।। इसे सदैव ZPP की परिभाषा के रूप में लिया जाता है। इसे दिखाने के लिए, पहले ध्यान दें कि प्रत्येक समस्या जो दोनों RP और co-RP में है, उसका लास वेगास एल्गोरिदम इस प्रकार है:

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

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

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

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

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

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

NP, RP और ZPP वर्गों को सेट में सदस्यता के प्रमाण के संदर्भ में सोचा जा सकता है।

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

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

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

टिप्पणियाँ:

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

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

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

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

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

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

' ZPP ' की तुलना 'BPP' से की जानी चाहिए। वर्ग 'BPP' को प्रमाण की आवश्यकता नहीं है, चूँकि प्रमाण पर्याप्त हैं (इसलिए 'BPP' में 'RP', 'co-RP' और ' ZPP ' सम्मिलित हैं)। BPP भाषा में V(x,w) अधिकांश स्ट्रिंग्स w पर स्वीकार होता है यदि x, X में है, और इसके विपरीत यदि x, X में नहीं है तो अधिकांश स्ट्रिंग्स w पर (स्पष्ट) अस्वीकार करता है। निश्चित हों, और इसलिए उन्हें सामान्यतः प्रमाण या गवाह नहीं माना जा सकता है ।

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

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

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

ZPP^NPBPP = ZPP^NP.

NP^BPP ZPP^NP में समाहित है।

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

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

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

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

यह भी देखें

• BPP
• RP

बाहरी संबंध

• Complexity Zoo: ZPP Class ZPP