ZPP (जटिलता): Difference between revisions

From Vigyanwiki
(Created page with "{{no footnotes|date=January 2013}} File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|अन्य संभाव्...")
 
No edit summary
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{no footnotes|date=January 2013}}
अन्य '''संभाव्य जटिलता''' वर्गों '''RP''', '''co-RP''', '''BPP''', [[बीक्यूपी|BQP]], '''PP'''[[पी (जटिलता)|)]], (जटिलता) के संबंध में ZPP , जो PSPACE के अंदर P (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध कठोर है या नहीं।
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|अन्य संभाव्य जटिलता वर्गों (आरपी ​​(जटिलता), सह-आरपी, [[बी[[पी[[पी (जटिलता)]]]]]], [[बीक्यूपी]], पीपी (जटिलता)) के संबंध में जेडपीपी, जो पीएसपीएसीई के भीतर पी (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध सख्त है या नहीं।]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ एक [[संभाव्य ट्यूरिंग मशीन]] मौजूद है:


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


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


वैकल्पिक रूप से, ZPP को उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके लिए इन गुणों के साथ एक संभाव्य ट्यूरिंग मशीन मौजूद है:
किन्तु और दूसरे शब्दों में, यदि एल्गोरिदम को चलने के समय वास्तव में यादृच्छिक सिक्का फ्लिप करने की अनुमति दी जाती है, तो यह सदैव सही उत्तर देता है और आकार ''n,'' की समस्या के लिए, कुछ बहुपद ''p''(''n'') है जैसे कि औसत चल रहा है समय ''p''(''n'') से कम होगा, भले ही यह कभी-कभी बहुत अधिक हो सकता है। ऐसे एल्गोरिथम को [[ लास वेगास एल्गोरिथ्म |लास वेगास एल्गोरिथ्म]] कहा जाता है।
 
इस प्रकार से वैकल्पिक रूप से, '''ZPP''' को उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके अतिरिक्त लिए इन गुणों के साथ एक संभाव्य ट्यूरिंग मशीन उपस्तिथ होते है:
* यह सदैव बहुपद समय में चलता है।
* यह सदैव बहुपद समय में चलता है।
* इसका उत्तर हां, नहीं या पता नहीं है।
* इसका उत्तर हां, नहीं या पता नहीं है।
* उत्तर हमेशा या तो पता नहीं या सही उत्तर होता है।
* उत्तर सदैव या तो पता नहीं या सही उत्तर होता है।
* यह प्रत्येक इनपुट के लिए अधिकतम 1/2 संभावना (और अन्यथा सही उत्तर) के साथ DO NOT KNOW लौटाता है।
* यह प्रत्येक इनपुट के लिए अधिकतम 1/2 संभाव्यता (और अन्यथा सही उत्तर) के साथ 'नहीं जानता' लौटाता है।
दोनों परिभाषाएँ समतुल्य हैं।
इस प्रकार से दोनों परिभाषाएँ समतुल्य होती हैं।


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


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


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


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


यह दिखाने के लिए कि ZPP आरपी इंटरसेक्ट सह-आरपी में समाहित है, मान लीजिए कि हमारे पास एक समस्या को हल करने के लिए लास वेगास एल्गोरिदम सी है। फिर हम निम्नलिखित आरपी एल्गोरिदम का निर्माण कर सकते हैं:
यह दिखाने के लिए कि ZPP '''RP''' इंटरसेक्ट '''co-RP''' में समाहित होते है, मान लीजिए कि हमारे पास समस्या को हल करने के लिए लास वेगास एल्गोरिदम C है। फिर हम निम्नलिखित '''RP''' एल्गोरिदम का निर्माण कर सकते हैं:
* C को उसके अपेक्षित रनिंग समय से कम से कम ''दोगुने'' तक चलाएँ। यदि यह कोई उत्तर देता है तो वह उत्तर दीजिए। यदि यह हमारे रोकने से पहले कोई उत्तर नहीं देता है, तो 'नहीं' दें।
* C को उसके अपेक्षित रनिंग समय से कम से कम ''दोगुने'' तक चलाएँ। यदि यह कोई उत्तर देता है तो वह उत्तर दीजिए। यदि यह हमारे रोकने से पहले कोई उत्तर नहीं देता है, तो 'नहीं' दें।
मार्कोव की असमानता|मार्कोव की असमानता से, हमारे रोकने से पहले इसका उत्तर मिलने की संभावना कम से कम 1/2 है। इसका मतलब यह है कि हाँ उदाहरण पर हम रुककर और 'नहीं' देकर गलत उत्तर देंगे, यह मौका अधिकतम 1/2 है, जो आरपी एल्गोरिथ्म की परिभाषा के अनुरूप है। सह-आरपी एल्गोरिथ्म समान है, सिवाय इसके कि यदि 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'') स्वीकार करता है;
* यदि ''x'' ''X'' में नहीं है, तो सभी स्ट्रिंग्स के लिए ''w'', ''V''(''x'',''w'') अस्वीकार कर देता है।
* यदि ''x'' ''X'' में नहीं है, तो सभी स्ट्रिंग्स के लिए ''w'', ''V''(''x'',''w'') अस्वीकार कर देता है।


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


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


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


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


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


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


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


== जटिलता-सैद्धांतिक गुण ==
== जटिलता-सैद्धांतिक गुण ==
यह ज्ञात है कि ZPP पूरक के तहत बंद है; अर्थात्, ZPP = सह-ZPP।
यह ज्ञात है कि ZPP पूरक के तहत बंद है; अर्थात्, ZPP = co-ZPP।


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


ZPP<sup>उदाहरण के लिए:<sup>BPP</sup></sup> = ZPP<sup>एनपी</sup>.
'''ZPP<sup>NPBPP</sup>''' = '''ZPP<sup>NP</sup>'''.


एनपी<sup>BPP</sup>ZPP में समाहित है<sup>एनपी</sup>.
'''NP<sup>BPP</sup>''' '''ZPP<sup>NP</sup>''' में समाहित है।


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


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


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


== यह भी देखें ==
== यह भी देखें ==
* बीपीपी (जटिलता)
* '''BPP'''
* आरपी (जटिलता)
* '''RP'''


==बाहरी संबंध==
==बाहरी संबंध==
Line 79: Line 80:


{{ComplexityClasses}}
{{ComplexityClasses}}
[[Category: संभाव्य जटिलता वर्ग]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 27/06/2023]]
[[Category:Created On 27/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:संभाव्य जटिलता वर्ग]]

Latest revision as of 21:42, 11 July 2023

अन्य संभाव्य जटिलता वर्गों 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 के लिए केवल यह आवश्यक है कि प्रमाण उपस्तिथ होते है । वे बहुत दुर्लभ हो सकते हैं. 2f(|x|) संभावित स्ट्रिंग, बहुपद के साथ f , सत्यापनकर्ता को स्वीकार करने के लिए केवल स्ट्रिंग की आवश्यकता होती है (यदि x, X में है। यदि x, X में नहीं है, तो कोई भी स्ट्रिंग सत्यापनकर्ता को स्वीकार करने का कारण नहीं बनेगी)।

अतः 'RP' और ' 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 ऑरेकल मशीन) इस अतिरिक्त शक्ति के बिना मशीन से अधिक शक्तिशाली नहीं है। प्रतीकों में, ZPPZPP = ZPP.

ZPPNPBPP = ZPPNP.

NPBPP ZPPNP में समाहित है।

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

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

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

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

यह भी देखें

  • BPP
  • RP

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ZPP_(जटिलता)&oldid=212876’