आरपी (जटिलता): Difference between revisions

Latest revision as of 09:35, 28 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⁻ⁿ	≤ 2⁻ⁿ
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 का अंश जो $M(x,y)=1$ संतुष्ट करता है 1/2 से अधिक या उसके बराबर है
सभी एक्स के लिए जो एल में नहीं है, और लंबाई p(|x|), $M(x,y)=0$ की सभी स्ट्रिंग्स y

इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा उत्तम है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है।

संबंधित जटिलता वर्ग

[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25| अन्य संभावित जटिलता वर्गों (जेडपीपी (जटिलता), सह-आरपी, बीपीपी (जटिलता), बीक्यूपी, पीपी (जटिलता)) के संबंध में आरपी, जो पीएसपीएसीई के अन्दर पी (जटिलता) को सामान्यीकृत करते हैं। यह ज्ञात नहीं है कि इनमें से कोई भी नियंत्रण सख्त है या नहीं। आरपी की परिभाषा कहती है कि हाँ-उत्तर सदैव सही होता है और कोई-उत्तर गलत नहीं हो सकता है, क्योंकि हाँ-उदाहरण ना-उत्तर लौटा सकता है। जटिलता वर्ग सह-आरपी पूरक है, जहां हाँ-उत्तर गलत हो सकता है, जबकि नहीं-उत्तर सदैव सही होता है।

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

पी और एनपी से कनेक्शन

Unsolved problem in computer science:

${\mathsf {P}}{\overset {?}{=}}{\mathsf {RP}}$

(more unsolved problems in computer science)

पी (जटिलता) आरपी का सबसमुच्चय है, जो एनपी (जटिलता) का सबसमुच्चय है। इसी तरह, P सह-आरपी का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। चूँकि, यदि सामान्यतः माना जाने वाला अनुमान P = BPP सत्य है, तो आरपी, सह-आरपी और P पतन (सभी समान हैं)। यह मानते हुए कि पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और सह-एनपी के प्रतिच्छेदन का उपसमुच्चय है, चूँकि यह पी = बीपीपी द्वारा निहित होगा।

सह-आरपी में समस्या का प्राकृतिक उदाहरण वर्तमान में पी में नहीं जाना जाता है, बहुपद पहचान परीक्षण है, यह तय करने की समस्या है कि पूर्णांकों पर दी गई बहुभिन्नरूपी अंकगणितीय अभिव्यक्ति शून्य-बहुपद है या नहीं। उदाहरण के लिए, x·x − y·y − (x + y)·(x − y) शून्य-बहुपद है जबकि x·x + y·y क्या नहीं है।

आरपी का वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, गैर-नियतात्मक ट्यूरिंग मशीन द्वारा पहचानने योग्य समस्याओं का समुच्चय होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल स्वीकार्य पथ की आवश्यकता होती है, जो पथों के घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि आरपी एनपी का उपसमुच्चय है।

यह भी देखें

यादृच्छिक एल्गोरिदम
बीपीपी (जटिलता)
जेडपीपी (जटिलता)

संदर्भ

↑ 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.

बाहरी संबंध

RP at the Complexity Zoo

[1] 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.

[1]

@@ Line 1: / Line 1: @@
 {{short description|Randomized polynomial time class of computational complexity theory}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, यादृच्छिक बहुपद समय (आरपी) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ एक [[संभाव्य ट्यूरिंग मशीन]] मौजूद है:
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल स्पष्टता सिद्धांत]] में, यादृच्छिक बहुपद समय (आरपी) समस्याओं का [[जटिलता वर्ग|स्पष्टता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्थित है:
 {|class="wikitable" style="float:right;text-align:center;margin-left:1em"
 !colspan="3"|RP algorithm (1 run)
@@ Line 50: / Line 50: @@
 | ≥ 1/2
 |}
-* यह हमेशा इनपुट आकार में बहुपद समय में चलता है
+* यह सदैव इनपुट आकार में बहुपद समय में चलता है
-* यदि सही उत्तर नहीं है, तो यह हमेशा नहीं देता है
+* यदि सही उत्तर नहीं है, तो यह सदैव नहीं देता है
 * यदि सही उत्तर हाँ है, तो यह कम से कम 1/2 संभावना के साथ हाँ लौटाता है (अन्यथा, यह नहीं देता है)।
-दूसरे शब्दों में, एल्गोरिथ्म को चलने के दौरान वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र मामला जिसमें [[ कलन विधि ]] YES लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; हालाँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना NO के साथ समाप्त हो सकता है। यही है, अगर एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है।
+दूसरे शब्दों में, एल्गोरिथ्म को चलने के समय वास्तव में यादृच्छिक सिक्का फ़्लिप करने की अनुमति है। एकमात्र स्थिति जिसमें [[ कलन विधि |एल्गोरिथम]] हाँ लौटा सकता है, यदि वास्तविक उत्तर हाँ है; इसलिए यदि एल्गोरिथ्म समाप्त हो जाता है और हाँ उत्पन्न करता है, तो सही उत्तर निश्चित रूप से हाँ है; चूँकि, एल्गोरिथ्म वास्तविक उत्तर की परवाह किए बिना नहीं के साथ समाप्त हो सकता है। यही है, यदि एल्गोरिदम नहीं लौटाता है, तो यह गलत हो सकता है।
-कुछ लेखक इस वर्ग को 'आर' कहते हैं, हालांकि यह नाम आमतौर पर [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है।
+कुछ लेखक इस वर्ग को 'आर' कहते हैं, चूँकि यह नाम सामान्यतः [[पुनरावर्ती भाषा]]ओं के वर्ग के लिए अधिक प्रयोग किया जाता है।
-यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम संभावना के साथ कम से कम एक बार YES लौटाएगा {{math|1 − 2<sup>−''n''</sup>}}. इसलिए यदि एल्गोरिथ्म को 100 बार चलाया जाता है, तो इसके हर बार गलत उत्तर देने की संभावना इस संभावना से कम होती है कि कॉस्मिक किरणें एल्गोरिथम चलाने वाले कंप्यूटर की मेमोरी को दूषित कर देती हैं।<ref>This comparison is attributed to [[Michael O. Rabin]] on p.&nbsp;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> इस अर्थ में, यदि यादृच्छिक संख्या का स्रोत उपलब्ध है, तो आरपी में अधिकांश एल्गोरिदम अत्यधिक व्यावहारिक हैं।
+यदि सही उत्तर हाँ है और प्रत्येक रन के परिणाम के साथ एल्गोरिथम को n बार चलाया जाता है, तो यह कम से कम {{math|1 − 2<sup>−''n''</sup>}} संभावना के साथ कम से कम एक बार हाँ लौटाएगा। इसलिए यदि एल्गोरिथ्म को 100 बार चलाया जाता है, तो इसके हर बार गलत उत्तर देने की संभावना इस संभावना से कम होती है कि कॉस्मिक किरणें एल्गोरिथम चलाने वाले कंप्यूटर की मेमोरी को दूषित कर देती हैं।<ref>This comparison is attributed to [[Michael O. Rabin]] on p.&nbsp;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 आउटपुट देता है
+* एल में सभी एक्स के लिए, एम 1/2 से अधिक या उसके बराबर प्रायिकता के साथ 1 आउटपुट देता है
 * एल में नहीं सभी एक्स के लिए, एम 0 आउटपुट करता है
-वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है अगर और केवल अगर वहाँ एक बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम मौजूद है, जैसे कि
+वैकल्पिक रूप से, 'आरपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। एक भाषा एल 'आरपी' में है यदि और केवल यदि वहाँ बहुपद पी और नियतात्मक ट्यूरिंग मशीन एम उपस्थित है, जैसे कि
 * एम सभी इनपुट पर बहुपद समय के लिए चलता है
-* L में सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है {{tmath|1=M(x,y) = 1}} 1/2 से अधिक या उसके बराबर है
+* एल में सभी एक्स के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो {{tmath|1=M(x,y) = 1}} संतुष्ट करता है 1/2 से अधिक या उसके बराबर है
-* सभी x के लिए जो L में नहीं है, और सभी स्ट्रिंग्स y की लंबाई p(|x|), {{tmath|1=M(x,y) = 0}}
+* सभी एक्स के लिए जो एल में नहीं है, और लंबाई p(|x|), {{tmath|1=M(x,y) = 0}} की सभी स्ट्रिंग्स y
-इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा बेहतर है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है।
+इस परिभाषा में, स्ट्रिंग y रैंडम कॉइन फ़्लिप के आउटपुट से मेल खाती है जिसे प्रोबेबिलिस्टिक ट्यूरिंग मशीन ने बनाया होगा। कुछ अनुप्रयोगों के लिए यह परिभाषा उत्तम है क्योंकि इसमें संभाव्य ट्यूरिंग मशीनों का उल्लेख नहीं है।
 == संबंधित जटिलता वर्ग ==
-[[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 के प्रतिच्छेदन को ZPP (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के बजाय सह-आर नाम का उपयोग करते हैं।
+वर्ग सीमाबद्ध-त्रुटि संभाव्य बहुपद एल्गोरिदम का वर्णन करता है जो हाँ और नहीं दोनों उदाहरणों पर गलत उत्तर दे सकता है, और इस प्रकार आरपी और सह-आरपी दोनों सम्मिलित हैं। समुच्चय आरपी और सह-आरपी के प्रतिच्छेदन को जेडपीपी (जटिलता) कहा जाता है। जैसे आरपी को आर कहा जा सकता है, कुछ लेखक सह-आरपी के अतिरिक्त सह-आर नाम का उपयोग करते हैं।
-== पी और एनपी == से कनेक्शन
+पी और एनपी  से कनेक्शन{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}}
-{{unsolved|computer science|{{tmath|1= \mathsf P \overset{?}{=} \mathsf{RP} }}}}
+पी (जटिलता) आरपी का सबसमुच्चय है, जो [[एनपी (जटिलता)]] का सबसमुच्चय है। इसी तरह, P सह-आरपी का उपसमुच्चय है जो सह-NP का उपसमुच्चय है। यह ज्ञात नहीं है कि ये समावेशन सख्त हैं या नहीं। चूँकि, यदि सामान्यतः माना जाने वाला अनुमान P = BPP सत्य है, तो आरपी, सह-आरपी और P पतन (सभी समान हैं)। यह मानते हुए कि पी ≠ एनपी, इसका मतलब यह है कि आरपी सख्ती से एनपी में निहित है। यह ज्ञात नहीं है कि आरपी = सह-आरपी, या आरपी एनपी और [[सह-एनपी]] के प्रतिच्छेदन का उपसमुच्चय है, चूँकि यह पी = बीपीपी द्वारा निहित होगा।
-पी (जटिलता) आरपी का एक सबसेट है, जो [[एनपी (जटिलता)]] का एक सबसेट है। इसी तरह, 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'')}} शून्य-बहुपद है जबकि {{nowrap|''x''·''x'' + ''y''·''y''}} क्या नहीं है।
-{{nowrap|''x''·''x'' + ''y''·''y''}} क्या नहीं है।
-आरपी का एक वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, [[गैर-नियतात्मक ट्यूरिंग मशीन]]ों द्वारा पहचानने योग्य समस्याओं का सेट होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल एक स्वीकार्य पथ की आवश्यकता होती है, जो पथों के एक घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि RP NP का एक उपसमुच्चय है।
+आरपी का वैकल्पिक लक्षण वर्णन जो कभी-कभी उपयोग करने में आसान होता है, [[गैर-नियतात्मक ट्यूरिंग मशीन]] द्वारा पहचानने योग्य समस्याओं का समुच्चय होता है, जहां मशीन इनपुट आकार से स्वतंत्र गणना पथ के कम से कम कुछ निरंतर अंश स्वीकार करती है, तो स्वीकार करती है। दूसरी ओर, एनपी को केवल स्वीकार्य पथ की आवश्यकता होती है, जो पथों के घातीय रूप से छोटे अंश का गठन कर सकता है। यह लक्षण वर्णन इस तथ्य को स्पष्ट करता है कि आरपी एनपी का उपसमुच्चय है।
 == यह भी देखें ==
 * यादृच्छिक एल्गोरिदम
 * बीपीपी (जटिलता)
-* ZPP (जटिलता)
+* जेडपीपी (जटिलता)
 ==संदर्भ==
 {{reflist}}
-{{refimprove|date=October 2014}}
 == बाहरी संबंध==
 *[https://complexityzoo.net/Complexity_Zoo:R#rp RP at the Complexity Zoo]
 {{ComplexityClasses}}
-[[Category: संभाव्य जटिलता वर्ग]]
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates]]
 [[Category:Created On 31/05/2023]]
+[[Category:Lua-based templates]]
+[[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 Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:संभाव्य जटिलता वर्ग]]

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

आरपी (जटिलता): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:35, 28 June 2023

Contents

औपचारिक परिभाषा

संबंधित जटिलता वर्ग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आरपी (जटिलता): Difference between revisions

Latest revision as of 09:35, 28 June 2023

औपचारिक परिभाषा

संबंधित जटिलता वर्ग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories