आरपी (जटिलता): Difference between revisions
No edit summary |
No edit summary |
||
| Line 54: | Line 54: | ||
* यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)। | * यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)। | ||
दूसरे शब्दों में, एल्गोरिथ्म को चलने के समय वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र स्थिति जिसमें [[ कलन विधि | एल्गोरिथम]] हाँ लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; चूँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना नहीं के साथ समाप्त हो सकता है। यही है, यदि एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है। | दूसरे शब्दों में, एल्गोरिथ्म को चलने के समय वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र स्थिति जिसमें [[ कलन विधि |एल्गोरिथम]] हाँ लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; चूँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना नहीं के साथ समाप्त हो सकता है। यही है, यदि एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है। | ||
कुछ लेखक इस वर्ग को 'आर' कहते हैं, चूँकि यह नाम सामान्यतः [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है। | कुछ लेखक इस वर्ग को 'आर' कहते हैं, चूँकि यह नाम सामान्यतः [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है। | ||
| Line 61: | Line 61: | ||
परिभाषा में अंश 1/2 इच्छानुसार है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, तथापि 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है। | परिभाषा में अंश 1/2 इच्छानुसार है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, तथापि 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
एक भाषा एल 'आरपी' में है यदि और केवल तभी संभावित ट्यूरिंग मशीन एम उपस्थित है, जैसे कि | एक भाषा एल 'आरपी' में है यदि और केवल तभी संभावित ट्यूरिंग मशीन एम उपस्थित है, जैसे कि | ||
* एम सभी इनपुट पर बहुपद समय के लिए चलता है | * एम सभी इनपुट पर बहुपद समय के लिए चलता है | ||
* एल में सभी एक्स | * एल में सभी एक्स के लिए, एम 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है | ||
* एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है | * एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है | ||
वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है यदि और केवल यदि वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम उपस्थित है, जैसे कि | वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है यदि और केवल यदि वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम उपस्थित है, जैसे कि | ||
* एम सभी इनपुट पर बहुपद समय के लिए चलता है | * एम सभी इनपुट पर बहुपद समय के लिए चलता है | ||
* एल में सभी एक्स | * एल में सभी एक्स के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो {{tmath|1=M(x,y) = 1}} संतुष्ट करता है 1/2 से अधिक या उसके बराबर है | ||
* सभी एक्स | * सभी एक्स के लिए जो एल में नहीं है, और लंबाई p(|x|), {{tmath|1=M(x,y) = 0}} की सभी स्ट्रिंग्स y | ||
इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा उत्तम है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है। | इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा उत्तम है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है। | ||
| Line 79: | Line 76: | ||
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25| अन्य संभावित जटिलता वर्गों (जेडपी[[पी (जटिलता)]], सह-आरपी, बी[[पीपी (जटिलता)]], [[बीक्यूपी]], पीपी (जटिलता)) के संबंध में आरपी, जो [[पीएसपीएसीई]] के अन्दर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं। आरपी की परिभाषा कहती है कि हाँ-उत्तर सदैव सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर सदैव सही होता है। | [[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25| अन्य संभावित जटिलता वर्गों (जेडपी[[पी (जटिलता)]], सह-आरपी, बी[[पीपी (जटिलता)]], [[बीक्यूपी]], पीपी (जटिलता)) के संबंध में आरपी, जो [[पीएसपीएसीई]] के अन्दर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं। आरपी की परिभाषा कहती है कि हाँ-उत्तर सदैव सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर सदैव सही होता है। | ||
वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों सम्मिलित हैं। समुच्चय आरपी और सह-आरपी के प्रतिच्छेदन को जेडपीपी | वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों सम्मिलित हैं। समुच्चय आरपी और सह-आरपी के प्रतिच्छेदन को जेडपीपी (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के अतिरिक्त सह-आर नाम का उपयोग करते हैं। | ||
पी और एनपी से कनेक्शन{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | पी और एनपी से कनेक्शन{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | ||
| Line 91: | Line 88: | ||
* यादृच्छिक एल्गोरिदम | * यादृच्छिक एल्गोरिदम | ||
* बीपीपी (जटिलता) | * बीपीपी (जटिलता) | ||
* जेडपीपी | * जेडपीपी (जटिलता) | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 01:43, 18 June 2023
कम्प्यूटेशनल स्पष्टता सिद्धांत में, यादृच्छिक बहुपद समय (आरपी) समस्याओं का स्पष्टता वर्ग है जिसके लिए इन गुणों के साथ संभाव्य ट्यूरिंग मशीन उपस्थित है:
| RP algorithm (1 run) | ||
|---|---|---|
Answer produced Correct
answer |
Yes | No |
| Yes | ≥ 1/2 | ≤ 1/2 |
| No | 0 | 1 |
| RP algorithm (n runs) | ||
Answer produced Correct
answer |
Yes | No |
| Yes | ≥ 1 − 2−n | ≤ 2−n |
| No | 0 | 1 |
| co-RP algorithm (1 run) | ||
Answer produced Correct
answer |
Yes | No |
| Yes | 1 | 0 |
| No | ≤ 1/2 | ≥ 1/2 |
- यह सदैव इनपुट आकार में बहुपद समय में चलता है
- यदि सही उत्तर नहीं है, तो यह सदैव नहीं देता है
- यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)।
दूसरे शब्दों में, एल्गोरिथ्म को चलने के समय वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र स्थिति जिसमें एल्गोरिथम हाँ लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; चूँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना नहीं के साथ समाप्त हो सकता है। यही है, यदि एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है।
कुछ लेखक इस वर्ग को 'आर' कहते हैं, चूँकि यह नाम सामान्यतः पुनरावर्ती भाषाओं के वर्ग के लिए अधिक प्रयोग किया जाता है।
यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम 1 − 2−n संभावना के साथ कम से कम एक बार हाँ लौटाएगा। इसलिए यदि एल्गोरिथ्म को 100 बार चलाया जाता है, तो इसके हर बार गलत उत्तर देने की संभावना इस संभावना से कम होती है कि कॉस्मिक किरणें एल्गोरिथम चलाने वाले कंप्यूटर की मेमोरी को दूषित कर देती हैं।[1] इस अर्थ में, यदि यादृच्छिक संख्या का स्रोत उपलब्ध है, तो आरपी में अधिकांश एल्गोरिदम अत्यधिक व्यावहारिक हैं।
परिभाषा में अंश 1/2 इच्छानुसार है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, तथापि 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है।
औपचारिक परिभाषा
एक भाषा एल 'आरपी' में है यदि और केवल तभी संभावित ट्यूरिंग मशीन एम उपस्थित है, जैसे कि
- एम सभी इनपुट पर बहुपद समय के लिए चलता है
- एल में सभी एक्स के लिए, एम 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है
- एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है
वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है यदि और केवल यदि वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम उपस्थित है, जैसे कि
- एम सभी इनपुट पर बहुपद समय के लिए चलता है
- एल में सभी एक्स के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है 1/2 से अधिक या उसके बराबर है
- सभी एक्स के लिए जो एल में नहीं है, और लंबाई p(|x|), की सभी स्ट्रिंग्स y
इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा उत्तम है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है।
संबंधित जटिलता वर्ग
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25| अन्य संभावित जटिलता वर्गों (जेडपीपी (जटिलता), सह-आरपी, बीपीपी (जटिलता), बीक्यूपी, पीपी (जटिलता)) के संबंध में आरपी, जो पीएसपीएसीई के अन्दर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं। आरपी की परिभाषा कहती है कि हाँ-उत्तर सदैव सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर सदैव सही होता है।
वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों सम्मिलित हैं। समुच्चय आरपी और सह-आरपी के प्रतिच्छेदन को जेडपीपी (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के अतिरिक्त सह-आर नाम का उपयोग करते हैं।
पी और एनपी से कनेक्शन
पी (जटिलता) आरपी का सबसेट है, जो एनपी (जटिलता) का सबसेट है। इसी तरह, P सह-आरपी का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। चूँकि, यदि सामान्यतः माना जाने वाला अनुमान P = BPP सत्य है, तो आरपी, सह-आरपी और P पतन (सभी समान हैं)। यह मानते हुए कि पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और सह-एनपी के चौराहे का उपसमुच्चय है, चूँकि यह पी = बीपीपी द्वारा निहित होगा।
सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, बहुपद पहचान परीक्षण है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, x·x − y·y − (x + y)·(x − y) शून्य-बहुपद है जबकि x·x + y·y क्या नहीं है।
आरपी का वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, गैर-नियतात्मक ट्यूरिंग मशीन द्वारा पहचानने योग्य समस्याओं का सेट होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल स्वीकार्य पथ की आवश्यकता होती है, जो पथों के घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि आरपी NP का उपसमुच्चय है।
यह भी देखें
- यादृच्छिक एल्गोरिदम
- बीपीपी (जटिलता)
- जेडपीपी (जटिलता)
संदर्भ
- ↑ This comparison is attributed to Michael O. Rabin on p. 252 of Gasarch, William (2014), "Classifying Problems into Complexity Classes", in Memon, Atif (ed.), Advances in Computers, Vol. 95 (PDF), Academic Press, pp. 239–292.
