आरपी (जटिलता): Difference between revisions
(Created page with "{{short description|Randomized polynomial time class of computational complexity theory}} कम्प्यूटेशनल जटिलता सिद्धांत...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Randomized polynomial time class of computational complexity theory}} | {{short description|Randomized polynomial time class of computational complexity theory}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, यादृच्छिक बहुपद समय (आरपी) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, यादृच्छिक बहुपद समय (आरपी) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] मौजूद है: | ||
{|class="wikitable" style="float:right;text-align:center;margin-left:1em" | {|class="wikitable" style="float:right;text-align:center;margin-left:1em" | ||
!colspan="3"|RP algorithm (1 run) | !colspan="3"|RP algorithm (1 run) | ||
| Line 63: | Line 63: | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
एक भाषा एल 'आरपी' में है अगर और केवल तभी | एक भाषा एल 'आरपी' में है अगर और केवल तभी संभावित ट्यूरिंग मशीन एम मौजूद है, जैसे कि | ||
* एम सभी इनपुट पर बहुपद समय के लिए चलता है | * एम सभी इनपुट पर बहुपद समय के लिए चलता है | ||
* L में सभी x के लिए, M 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है | * L में सभी x के लिए, M 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है | ||
* एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है | * एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है | ||
वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है अगर और केवल अगर वहाँ | वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है अगर और केवल अगर वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम मौजूद है, जैसे कि | ||
* एम सभी इनपुट पर बहुपद समय के लिए चलता है | * एम सभी इनपुट पर बहुपद समय के लिए चलता है | ||
* L में सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है {{tmath|1=M(x,y) = 1}} 1/2 से अधिक या उसके बराबर है | * L में सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है {{tmath|1=M(x,y) = 1}} 1/2 से अधिक या उसके बराबर है | ||
| Line 75: | Line 75: | ||
== संबंधित जटिलता वर्ग == | == संबंधित जटिलता वर्ग == | ||
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|अन्य संभावित जटिलता वर्गों (जेडपी[[पी (जटिलता)]], सह-आरपी, [[बी[[पीपी (जटिलता)]]]], [[बीक्यूपी]], पीपी (जटिलता)) के संबंध में आरपी, जो [[पीएसपीएसीई]] के भीतर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं।]]RP की परिभाषा कहती है कि हाँ-उत्तर हमेशा सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां | [[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|अन्य संभावित जटिलता वर्गों (जेडपी[[पी (जटिलता)]], सह-आरपी, [[बी[[पीपी (जटिलता)]]]], [[बीक्यूपी]], पीपी (जटिलता)) के संबंध में आरपी, जो [[पीएसपीएसीई]] के भीतर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं।]]RP की परिभाषा कहती है कि हाँ-उत्तर हमेशा सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर हमेशा सही होता है। | ||
वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों शामिल हैं। समुच्चय RP और सह-RP के प्रतिच्छेदन को ZPP (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के बजाय सह-आर नाम का उपयोग करते हैं। | वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों शामिल हैं। समुच्चय RP और सह-RP के प्रतिच्छेदन को ZPP (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के बजाय सह-आर नाम का उपयोग करते हैं। | ||
| Line 81: | Line 81: | ||
== पी और एनपी == से कनेक्शन | == पी और एनपी == से कनेक्शन | ||
{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | {{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | ||
पी (जटिलता) आरपी का | पी (जटिलता) आरपी का सबसेट है, जो [[एनपी (जटिलता)]] का सबसेट है। इसी तरह, P सह-RP का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। हालाँकि, यदि आमतौर पर माना जाने वाला अनुमान P = BPP सत्य है, तो RP, सह-RP और P पतन (सभी समान हैं)। यह मानते हुए कि पी = एनपी समस्या | पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और [[सह-एनपी]] के चौराहे का उपसमुच्चय है, हालांकि यह पी = बीपीपी द्वारा निहित होगा। | ||
सह-आरपी में | सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, [[बहुपद पहचान परीक्षण]] है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, {{nowrap|''x''·''x'' − ''y''·''y'' − (''x'' + ''y'')·(''x'' − ''y'')}} शून्य-बहुपद है जबकि | ||
{{nowrap|''x''·''x'' + ''y''·''y''}} क्या नहीं है। | {{nowrap|''x''·''x'' + ''y''·''y''}} क्या नहीं है। | ||
आरपी का | आरपी का वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, [[गैर-नियतात्मक ट्यूरिंग मशीन]]ों द्वारा पहचानने योग्य समस्याओं का सेट होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल स्वीकार्य पथ की आवश्यकता होती है, जो पथों के घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि RP NP का उपसमुच्चय है। | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 95: | Line 95: | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
== बाहरी संबंध== | == बाहरी संबंध== | ||
*[https://complexityzoo.net/Complexity_Zoo:R#rp RP at the Complexity Zoo] | *[https://complexityzoo.net/Complexity_Zoo:R#rp RP at the Complexity Zoo] | ||
Revision as of 01:02, 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 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)।
दूसरे शब्दों में, एल्गोरिथ्म को चलने के दौरान वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र मामला जिसमें कलन विधि YES लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; हालाँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना NO के साथ समाप्त हो सकता है। यही है, अगर एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है।
कुछ लेखक इस वर्ग को 'आर' कहते हैं, हालांकि यह नाम आमतौर पर पुनरावर्ती भाषाओं के वर्ग के लिए अधिक प्रयोग किया जाता है।
यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम संभावना के साथ कम से कम एक बार YES लौटाएगा 1 − 2−n. इसलिए यदि एल्गोरिथ्म को 100 बार चलाया जाता है, तो इसके हर बार गलत उत्तर देने की संभावना इस संभावना से कम होती है कि कॉस्मिक किरणें एल्गोरिथम चलाने वाले कंप्यूटर की मेमोरी को दूषित कर देती हैं।[1] इस अर्थ में, यदि यादृच्छिक संख्या का स्रोत उपलब्ध है, तो आरपी में अधिकांश एल्गोरिदम अत्यधिक व्यावहारिक हैं।
परिभाषा में अंश 1/2 मनमाना है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, भले ही 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है।
औपचारिक परिभाषा
एक भाषा एल 'आरपी' में है अगर और केवल तभी संभावित ट्यूरिंग मशीन एम मौजूद है, जैसे कि
- एम सभी इनपुट पर बहुपद समय के लिए चलता है
- L में सभी x के लिए, M 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है
- एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है
वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है अगर और केवल अगर वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम मौजूद है, जैसे कि
- एम सभी इनपुट पर बहुपद समय के लिए चलता है
- L में सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है 1/2 से अधिक या उसके बराबर है
- सभी x के लिए जो L में नहीं है, और सभी स्ट्रिंग्स y की लंबाई p(|x|),
इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा बेहतर है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है।
संबंधित जटिलता वर्ग
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|अन्य संभावित जटिलता वर्गों (जेडपीपी (जटिलता), सह-आरपी, [[बीपीपी (जटिलता)]], बीक्यूपी, पीपी (जटिलता)) के संबंध में आरपी, जो पीएसपीएसीई के भीतर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं।]]RP की परिभाषा कहती है कि हाँ-उत्तर हमेशा सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर हमेशा सही होता है।
वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों शामिल हैं। समुच्चय RP और सह-RP के प्रतिच्छेदन को ZPP (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के बजाय सह-आर नाम का उपयोग करते हैं।
== पी और एनपी == से कनेक्शन
पी (जटिलता) आरपी का सबसेट है, जो एनपी (जटिलता) का सबसेट है। इसी तरह, P सह-RP का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। हालाँकि, यदि आमतौर पर माना जाने वाला अनुमान P = BPP सत्य है, तो RP, सह-RP और P पतन (सभी समान हैं)। यह मानते हुए कि पी = एनपी समस्या | पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और सह-एनपी के चौराहे का उपसमुच्चय है, हालांकि यह पी = बीपीपी द्वारा निहित होगा।
सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, बहुपद पहचान परीक्षण है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, x·x − y·y − (x + y)·(x − y) शून्य-बहुपद है जबकि x·x + y·y क्या नहीं है।
आरपी का वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, गैर-नियतात्मक ट्यूरिंग मशीनों द्वारा पहचानने योग्य समस्याओं का सेट होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल स्वीकार्य पथ की आवश्यकता होती है, जो पथों के घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि RP NP का उपसमुच्चय है।
यह भी देखें
- यादृच्छिक एल्गोरिदम
- बीपीपी (जटिलता)
- ZPP (जटिलता)
संदर्भ
- ↑ 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.
