आरपी (जटिलता): Difference between revisions
No edit summary |
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 50: | Line 50: | ||
| ≥ 1/2 | | ≥ 1/2 | ||
|} | |} | ||
* यह | * यह सदैव इनपुट आकार में बहुपद समय में चलता है | ||
* यदि सही उत्तर नहीं है, तो यह | * यदि सही उत्तर नहीं है, तो यह सदैव नहीं देता है | ||
* यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)। | * यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)। | ||
दूसरे शब्दों में, एल्गोरिथ्म को चलने के | दूसरे शब्दों में, एल्गोरिथ्म को चलने के समय वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र स्थिति जिसमें [[ कलन विधि | एल्गोरिथम]] हाँ लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; चूँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना नहीं के साथ समाप्त हो सकता है। यही है, यदि एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है। | ||
कुछ लेखक इस वर्ग को 'आर' कहते हैं, हालांकि यह नाम आमतौर पर [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है। | कुछ लेखक इस वर्ग को 'आर' कहते हैं, हालांकि यह नाम आमतौर पर [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है। | ||
यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम संभावना के साथ कम से कम एक बार | यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम संभावना के साथ कम से कम एक बार हाँ लौटाएगा {{math|1 − 2<sup>−''n''</sup>}}. इसलिए यदि एल्गोरिथ्म को 100 बार चलाया जाता है, तो इसके हर बार गलत उत्तर देने की संभावना इस संभावना से कम होती है कि कॉस्मिक किरणें एल्गोरिथम चलाने वाले कंप्यूटर की मेमोरी को दूषित कर देती हैं।<ref>This comparison is attributed to [[Michael O. Rabin]] on p. 252 of {{citation|contribution=Classifying Problems into Complexity Classes|first=William|last=Gasarch|url=http://www.cs.umd.edu/~gasarch/COURSES/452/F14/mysurvey.pdf|pages=239–292| author1-link=William Gasarch | title=Advances in Computers, Vol. 95|editor-first=Atif|editor-last=Memon|publisher=Academic Press|year=2014}}.</ref> इस अर्थ में, यदि यादृच्छिक संख्या का स्रोत उपलब्ध है, तो आरपी में अधिकांश एल्गोरिदम अत्यधिक व्यावहारिक हैं। | ||
परिभाषा में अंश 1/2 मनमाना है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, भले ही 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है। | परिभाषा में अंश 1/2 मनमाना है। सेट आरपी में ठीक वैसी ही समस्याएं होंगी, भले ही 1/2 को 1 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है। | ||
'''हीं लौटाता है, तो यह गलत हो सकता है।''' | |||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
एक भाषा एल 'आरपी' में है | एक भाषा एल 'आरपी' में है यदि और केवल तभी संभावित ट्यूरिंग मशीन एम उपस्थित है, जैसे कि | ||
* एम सभी इनपुट पर बहुपद समय के लिए चलता है | * एम सभी इनपुट पर बहुपद समय के लिए चलता है | ||
* 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 77: | ||
== संबंधित जटिलता वर्ग == | == संबंधित जटिलता वर्ग == | ||
[[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 83: | ||
== पी और एनपी == से कनेक्शन | == पी और एनपी == से कनेक्शन | ||
{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | {{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}} | ||
पी (जटिलता) आरपी का सबसेट है, जो [[एनपी (जटिलता)]] का सबसेट है। इसी तरह, P सह-RP का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। | पी (जटिलता) आरपी का सबसेट है, जो [[एनपी (जटिलता)]] का सबसेट है। इसी तरह, P सह-RP का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। चूँकि, यदि आमतौर पर माना जाने वाला अनुमान P = BPP सत्य है, तो RP, सह-RP और P पतन (सभी समान हैं)। यह मानते हुए कि पी = एनपी समस्या | पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और [[सह-एनपी]] के चौराहे का उपसमुच्चय है, हालांकि यह पी = बीपीपी द्वारा निहित होगा। | ||
सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, [[बहुपद पहचान परीक्षण]] है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, {{nowrap|''x''·''x'' − ''y''·''y'' − (''x'' + ''y'')·(''x'' − ''y'')}} शून्य-बहुपद है जबकि | सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, [[बहुपद पहचान परीक्षण]] है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, {{nowrap|''x''·''x'' − ''y''·''y'' − (''x'' + ''y'')·(''x'' − ''y'')}} शून्य-बहुपद है जबकि | ||
Revision as of 01:10, 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 से कम किसी निरंतर गैर-शून्य संभावना से बदल दिया जाए; यहाँ स्थिरांक का अर्थ एल्गोरिथम के इनपुट से स्वतंत्र है।
हीं लौटाता है, तो यह गलत हो सकता है।
औपचारिक परिभाषा
एक भाषा एल 'आरपी' में है यदि और केवल तभी संभावित ट्यूरिंग मशीन एम उपस्थित है, जैसे कि
- एम सभी इनपुट पर बहुपद समय के लिए चलता है
- 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.
