बीपीपी (जटिलता)

कम्प्यूटेशनल जटिलता सिद्धांत में, कंप्यूटर विज्ञान की शाखा, सीमाबद्ध-त्रुटि संभाव्य बहुपद समय (बीपीपी) सभी उदाहरणों के लिए 1/3 से बंधी त्रुटि संभावना के साथ बहुपद समय में संभाव्य ट्यूरिंग मशीन द्वारा समाधान करने योग्य निर्णय समस्याओं का वर्ग है। बीपीपी समस्याओं के सबसे बड़े व्यावहारिक वर्गों में से है, जिसका अर्थ है कि बीपीपी में रुचि की अधिकांश समस्याओं में कुशल संभाव्य एल्गोरिदम हैं जिन्हें वास्तविक आधुनिक मशीनों पर शीघ्रता से चलाया जा सकता है। बीपीपी में P (जटिलता) भी सम्मिलित है, जो नियतात्मक मशीन के साथ बहुपद समय में समाधान करने योग्य समस्याओं का वर्ग है, क्योंकि नियतात्मक मशीन संभाव्य मशीन की विशेष स्थिति है।

बीपीपी एल्गोरिदम (1 रन)
Answer produced Correct answer	Yes	No
Yes	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3
बीपीपी एल्गोरिदम (k रन)
Answer produced Correct answer	Yes	No
Yes	> 1 − 2^−ck	< 2^−ck
No	< 2^−ck	> 1 − 2^−ck
for some constant c > 0

अनौपचारिक रूप से, समस्या बीपीपी में है यदि इसके लिए कोई एल्गोरिदम है जिसमें निम्नलिखित गुण हैं:

इसमें सिक्के उछालने और यादृच्छिक निर्णय लेने की अनुमति है।
इसके बहुपद समय में चलने का आश्वासन है।
एल्गोरिदम के किसी भी दिए गए रन पर, त्रुटिपूर्ण उत्तर देने की अधिकतम 1/3 संभावना होती है, चाहे उत्तर हाँ हो या नहीं।

परिभाषा

भाषा L 'बीपीपी' में है यदि और केवल तभी जब कोई संभाव्य ट्यूरिंग मशीन M उपस्थित हो, जैसे कि

M सभी इनपुट पर बहुपद समय के लिए चलता है।
L में सभी x के लिए, M 2/3 से अधिक या उसके समान संभावना के साथ 1 आउटपुट देता है।
L में नहीं सभी x के लिए, M 1/3 से कम या उसके समान संभावना के साथ 1 आउटपुट देता है।

जटिलता वर्ग 'जेडपीपी' के विपरीत, मशीन M को यादृच्छिक सिक्का फ्लिप के परिणाम की विचार किए बिना, सभी इनपुट पर बहुपद समय तक चलने की आवश्यकता होती है।

वैकल्पिक रूप से, 'बीपीपी' को केवल नियतात्मक ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। भाषा L 'बीपीपी' में है यदि और केवल तभी जब बहुपद p और नियतात्मक ट्यूरिंग मशीन M उपस्थित हो, जैसे कि;

M सभी इनपुट पर बहुपद समय के लिए चलता है।
L में सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है $M(x,y)=1$ 2/3 से बड़ा या उसके समान है।
L में नहीं सभी x के लिए, लंबाई p(|x|) की स्ट्रिंग y का अंश जो संतुष्ट करता है $M(x,y)=1$ 1/3 से कम या उसके समान है।

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

व्यवहार में, 1/3 की त्रुटि संभावना स्वीकार्य नहीं हो सकती है, चूँकि, परिभाषा में 1/3 का विकल्प इच्छानुसार है। 1/3 के स्थान पर 0 और 1/2 (अनन्य) के मध्य किसी भी गणितीय स्थिरांक का उपयोग करने के लिए परिभाषा को संशोधित करने से परिणामी सेट 'बीपीपी' परिवर्तित नहीं होता है। उदाहरण के लिए, यदि किसी ने वर्ग को इस प्रतिबंध के साथ परिभाषित किया है कि एल्गोरिदम अधिकतम 1/2¹⁰⁰ संभावना के साथ त्रुटिपूर्ण हो सकता है, तो इसके परिणामस्वरूप समस्याओं का एक ही वर्ग उत्पन्न होगा। त्रुटि संभावना का स्थिर होना भी आवश्यक नहीं है: समस्याओं के समान वर्ग को एक ओर 1/2 - n^-c जितनी उच्च त्रुटि की अनुमति देकर, या दूसरी ओर 2^{-n^c} जितनी छोटी त्रुटि की आवश्यकता के द्वारा परिभाषित किया जाता है, जहां c कोई धनात्मक स्थिरांक है, और n इनपुट की लंबाई है। त्रुटि संभावना की रूचि में यह लचीलापन त्रुटि-प्रवण एल्गोरिदम को कई बार चलाने और अधिक त्रुटिहीन एल्गोरिदम प्राप्त करने के लिए रन के बहुमत परिणाम का उपयोग करने के विचार पर आधारित है। चेरनॉफ बाउंड के परिणामस्वरूप अधिकांश रन त्रुटिपूर्ण होने की संभावना शीघ्रता से क्षय हो जाती है।^[1]

समस्याएँ

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

P में सभी समस्याएं स्पष्ट रूप से बीपीपी में भी हैं। चूँकि, कई समस्याओं के सम्बन्ध में ज्ञात हुआ है कि वे बीपीपी में हैं, किन्तु P में नहीं हैं। ऐसी समस्याओं की संख्या अल्प हो रही है, और यह अनुमान लगाया गया है कि P = BPP है।

लंबे समय से, सबसे प्रसिद्ध समस्याओं में से जिसे बीपीपी में जाना जाता था किन्तु P में नहीं जाना जाता था, वह निर्धारित करने की समस्या थी कि क्या कोई दी गई संख्या अभाज्य है या नहीं। चूँकि, 2002 के पेपर प्राइम्स पी में है, मनिन्द्र अग्रवाल और उनके छात्रों नीरज कयाल औरनितिन सक्सैना ने इस समस्या के लिए नियतात्मक बहुपद-समय एल्गोरिदम पाया, जिससे ज्ञात हुआ कि यह P में है।

बीपीपी (वास्तव में सह-आरपी) में समस्या का महत्वपूर्ण उदाहरण अभी भी P में नहीं जाना जाता है, बहुपद पहचान परीक्षण है, यह निर्धारित करने की समस्या है कि क्या बहुपद शून्य बहुपद के समान है, जब आप किसी दिए गए इनपुट के लिए बहुपद के मान तक पहुंच है, किन्तु गुणांक तक नहीं। दूसरे शब्दों में, क्या चरों के लिए मानों का कोई असाइनमेंट है जिससे कि जब इन मानों पर गैर-शून्य बहुपद का मूल्यांकन किया जाए, तो परिणाम गैर-शून्य हो? परिबद्ध त्रुटि संभावना प्राप्त करने के लिए कम से कम d मानों के परिमित उपसमुच्चय से यादृच्छिक रूप से प्रत्येक चर के मान का समान रूप से चयन करना पर्याप्त है, जहां d बहुपद की कुल डिग्री है।^[2]

जटिलता-सैद्धांतिक गुण

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

पी (जटिलता), एनपी (जटिलता), सह-एनपी, बीपीपी (जटिलता), पी/पॉली, पीएच (जटिलता), और पीएसपीएसीई सहित जटिलता वर्गों का समावेश

यह ज्ञात है कि बीपीपी पूरक के अंतर्गत संवृत है; अर्थात्, BPP = co-BPP है। बीपीपी अपने आप में कम है, जिसका अर्थ है कि बीपीपी समस्याओं को शीघ्र समाधान करने की शक्ति वाली बीपीपी मशीन (बीपीपी ओरेकल मशीन) इस अतिरिक्त शक्ति के बिना मशीन से अधिक शक्तिशाली नहीं है। प्रतीकों में, BPP^BPP = BPP है।

बीपीपी और एनपी (जटिलता) के मध्य संबंध अज्ञात है: यह ज्ञात नहीं है कि बीपीपी एनपी (जटिलता) का उपसमूह है या नहीं, एनपी बीपीपी का उपसमूह है या नहीं। यदि एनपी बीपीपी में समाहित है, जिसे असंभावित माना जाता है क्योंकि यह एनपी-पूर्ण समस्याओं के लिए व्यावहारिक समाधान प्रदान करेगा, तो एनपी = आरपी और पीएच (जटिलता) ⊆ बीपीपी।^[4] यह ज्ञात है कि आरपी (जटिलता) बीपीपी का उपसमूह है, और बीपीपी पीपी (जटिलता) का उपसमूह है। यह ज्ञात नहीं है कि क्या वे दोनों सख्त उपसमुच्चय हैं, क्योंकि हम यह भी नहीं जानते हैं कि क्या P, PSPACE का सख्त उपसमुच्चय है। BPP बहुपद पदानुक्रम के दूसरे स्तर में समाहित है और इसलिए यह PH में समाहित है। अधिक सटीक रूप से, सिप्सर-लौटेमैन प्रमेय यह बताता है ${\mathsf {BPP}}\subseteq \Sigma _{2}\cap \Pi _{2}$ . परिणामस्वरूप, P = NP, P = BPP की ओर ले जाता है क्योंकि इस स्थिति में PH घटकर P हो जाता है। इस प्रकार या तो P = BPP या P ≠ NP या दोनों।

एडलमैन के प्रमेय में कहा गया है कि बीपीपी में किसी भी भाषा में सदस्यता बहुपद आकार के बूलियन सर्किट के परिवार द्वारा निर्धारित की जा सकती है, जिसका अर्थ है कि बीपीपी पी/पॉली में निहित है।^[5] दरअसल, इस तथ्य के प्रमाण के परिणामस्वरूप, बंधी हुई लंबाई के इनपुट पर काम करने वाले प्रत्येक बीपीपी एल्गोरिदम को यादृच्छिक बिट्स की निश्चित स्ट्रिंग का उपयोग करके नियतात्मक एल्गोरिदम में यादृच्छिक किया जा सकता है। चूँकि , इस स्ट्रिंग को ढूँढना महंगा हो सकता है। मोंटे कार्लो समय कक्षाओं के लिए कुछ कमजोर पृथक्करण परिणाम सिद्ध हुए Karpinski & Verbeek (1987a), यह सभी देखें Karpinski & Verbeek (1987b).

समापन गुण

वर्ग BPP पूरकता, संघ और प्रतिच्छेदन के अंतर्गत बंद है।

सापेक्षीकरण

दैवज्ञों के संबंध में, हम जानते हैं कि दैवज्ञ ए और बी उपस्थित हैं, जैसे कि पी^ए = बीपीपी और पी बी बीपीपी बी. इसके अलावा, संभाव्यता 1 के साथ यादृच्छिक दैवज्ञ के सापेक्ष, पी = बीपीपी और बीपीपी सख्ती से एनपी और सह-एनपी में निहित है।^[6] यहाँ तक कि दैवज्ञ भी है जिसमें BPP=EXP एनपी(और इसलिए P<NP<BPP=EXP=NEXP),^[7] जिसे निम्नानुसार पुनरावृत्तीय रूप से निर्मित किया जा सकता है। निश्चित ई (जटिलता) के लिए एनपी (सापेक्षिक) पूर्ण समस्या, यदि समस्या के उदाहरण के साथ लंबाई kn (n उदाहरण की लंबाई है; k उपयुक्त छोटा स्थिरांक है) की यादृच्छिक स्ट्रिंग के साथ पूछताछ की जाती है, तो ओरेकल उच्च संभावना के साथ सही उत्तर देगा। n=1 से प्रारंभ करें. लंबाई n की समस्या के प्रत्येक उदाहरण के लिए इंस्टेंस आउटपुट को ठीक करने के लिए ओरेकल उत्तरों को ठीक करें (नीचे लेम्मा देखें)। इसके पश्चात, kn-लंबाई स्ट्रिंग के पश्चात वाले उदाहरण वाले प्रश्नों के लिए उदाहरण आउटपुट प्रदान करें, और फिर लंबाई ≤(k+1)n की क्वेरी के लिए आउटपुट को निश्चित मानें, और लंबाई n+1 के उदाहरणों के साथ आगे बढ़ें।

'लेम्मा:' सापेक्ष ई में समस्या (विशेष रूप से, ओरेकल मशीन कोड और समय की कमी) को देखते हुए एनपी , प्रत्येक आंशिक रूप से निर्मित ओरेकल और लंबाई n के इनपुट के लिए, आउटपुट को 2 निर्दिष्ट करके तय किया जा सकता है ओरेकल उत्तर देता है।
'प्रमाण:' मशीन सिम्युलेटेड है, और ओरेकल उत्तर (जो पसमाधाने से तय नहीं हैं) चरण-दर-चरण तय किए जाते हैं। प्रति नियतात्मक संगणना चरण में अधिकतम ओरेकल क्वेरी होती है। रिलेटिवाइज्ड एनपी ओरेकल के लिए, यदि संभव हो तो गणना पथ चुनकर और बेस ओरेकल के उत्तरों को ठीक करके आउटपुट को हां में ठीक करें; अन्यथा कोई फिक्सिंग आवश्यक नहीं है, और किसी भी तरह से प्रति चरण बेस ऑरेकल का अधिकतम 1 उत्तर होता है। चूंकि 2 हैं कदम, लेम्मा अनुसरण करता है।

लेम्मा यह सुनिश्चित करता है कि (पर्याप्त बड़े k के लिए), सापेक्ष E के लिए पर्याप्त तार छोड़ते हुए निर्माण करना संभव है एनपी उत्तर। इसके अलावा, हम यह सुनिश्चित कर सकते हैं कि सापेक्ष ई के लिए^एनपी, रैखिक समय पर्याप्त है, यहां तक कि फ़ंक्शन समस्याओं के लिए (यदि फ़ंक्शन ओरेकल और रैखिक आउटपुट आकार दिया गया है) और तेजी से छोटी (रैखिक घातांक के साथ) त्रुटि संभावना के साथ। इसके अलावा, यह निर्माण इस मायने में प्रभावी है कि मनमाना दैवज्ञ ए दिए जाने पर हम दैवज्ञ बी को पी के लिए व्यवस्थित कर सकते हैं ए पी बी और उदाहरण के लिए:ए उदाहरण के लिए: बी बी. इसके अलावा, ZPP (जटिलता) दैवज्ञ (और इसलिए ZPP=BPP=EXP<NEXP) के लिए, कोई सापेक्ष ई गणना में उत्तरों को विशेष गैर-उत्तर में ठीक कर देगा, इस प्रकार यह सुनिश्चित करेगा कि कोई नकली उत्तर नहीं दिया जाएगा।

व्युत्पन्नकरण

क्षेत्र के अधिकांश विशेषज्ञों द्वारा कुछ स्थिर छद्म यादृच्छिक संख्या जनरेटरों के अस्तित्व का अनुमान लगाया गया है। इस अनुमान का तात्पर्य है कि यादृच्छिकता बहुपद समय गणना को अतिरिक्त कम्प्यूटेशनल शक्ति नहीं देती है, अर्थात, P = RP = BPP है। ध्यान दें कि साधारण जनरेटर इस परिणाम को दिखाने के लिए पर्याप्त नहीं हैं; विशिष्ट यादृच्छिक संख्या जनरेटर का उपयोग करके कार्यान्वित कोई भी संभाव्य एल्गोरिदम मूल के अतिरिक्त कुछ इनपुट पर सदैव त्रुटिपूर्ण परिणाम देगा (चूँकि ये इनपुट दुर्लभ हो सकते हैं)।

लास्ज़लो बाबई, लांस फ़ोर्टनो, नोम निसान और एवी विगडर्सन ने दिखाया कि जब तक ऍक्स्पटाइम एमए तक सीमित नहीं हो जाता, बीपीपी इसमें समाहित है^[8]

: ${\textsf {i.o.-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {i.o.-DTIME}}\left(2^{n^{\varepsilon }}\right)$

वर्ग i.o.-SUBEXP, जिसका अर्थ अनंत बार SUBEXP है, में ऐसी समस्याएं हैं जिनमें अनंत रूप से कई इनपुट आकारों के लिए उप-घातांकीय समय एल्गोरिदम हैं। उन्होंने यह भी दिखाया कि P = BPP यदि घातीय-समय पदानुक्रम है जिसे बहुपद पदानुक्रम और E को E^PH के रूप में परिभाषित किया गया है, E तक पतन हो जाता है; चूँकि, ध्यान दें कि घातीय-समय पदानुक्रम को सामान्यतः पतन के लिए नहीं होने का अनुमान लगाया जाता है।

रसेल इम्पाग्लिआज़ो और एवी विगडर्सन ने दिखाया कि यदि E में कोई समस्या है, तो जहाँ;

{\mathsf {E}}={\mathsf {DTIME}}\left(2^{O(n)}\right)

इसमें सर्किट जटिलता 2^Ω(n) है, तो P = BPP है।^[9]

यह भी देखें

आरपी
जेडपीपी
बीक्यूपी
जटिलता वर्गों की सूची

संदर्भ

↑ Valentine Kabanets, CMPT 710 - Complexity Theory: Lecture 16, October 28, 2003
↑ Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003.
↑ "Complexity Zoo:B - Complexity Zoo".
↑ Lance Fortnow, Pulling Out The Quantumness, December 20, 2005
↑ Adleman, L. M. (1978). "यादृच्छिक बहुपद समय पर दो प्रमेय". Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing. pp. 75–83.
↑ Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing, 10 (1): 96–113, doi:10.1137/0210008, ISSN 1095-7111
↑ Heller, Hans (1986), "On relativized exponential and probabilistic complexity classes", Information and Control, 71 (3): 231–243, doi:10.1016/S0019-9958(86)80012-2
↑ Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi (1993). "'बीपीपी में उप-घातांकीय समय सिमुलेशन है जब तक कि एक्सपीटीआईएमई में प्रकाशन योग्य प्रमाण न हों". Computational Complexity. 3 (4): 307–318. doi:10.1007/bf01275486. S2CID 14802332.
↑ Russell Impagliazzo and Avi Wigderson (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590

Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 10.2.1: The class BPP, pp. 336–339.
Karpinski, Marek; Verbeek, Rutger (1987a). "Randomness, provability, and the separation of Monte Carlo time and space". In Börger, Egon (ed.). Computation Theory and Logic, In Memory of Dieter Rödding. Lecture Notes in Computer Science. Vol. 270. Springer. pp. 189–207. doi:10.1007/3-540-18170-9_166.
Karpinski, Marek; Verbeek, Rutger (1987b). "On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes". Information and Computation. 75 (2): 178–189. doi:10.1016/0890-5401(87)90057-5.
Arora, Sanjeev; Boaz Barak (2009). "Computational Complexity: A Modern Approach".

बाहरी संबंध

Princeton CS 597E: Derandomization paper list
Harvard CS 225: Pseudorandomness Archived 2003-08-05 at the Wayback Machine

[1] Valentine Kabanets, CMPT 710 - Complexity Theory: Lecture 16, October 28, 2003

[2] Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003.

[3] "Complexity Zoo:B - Complexity Zoo".

[4] Lance Fortnow, Pulling Out The Quantumness, December 20, 2005

[5] Adleman, L. M. (1978). "यादृच्छिक बहुपद समय पर दो प्रमेय". Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing. pp. 75–83.

[6] Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing, 10 (1): 96–113, doi:10.1137/0210008, ISSN 1095-7111

[7] Heller, Hans (1986), "On relativized exponential and probabilistic complexity classes", Information and Control, 71 (3): 231–243, doi:10.1016/S0019-9958(86)80012-2

[Babai-8] Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi (1993). "'बीपीपी में उप-घातांकीय समय सिमुलेशन है जब तक कि एक्सपीटीआईएमई में प्रकाशन योग्य प्रमाण न हों". Computational Complexity. 3 (4): 307–318. doi:10.1007/bf01275486. S2CID 14802332.

[9] Russell Impagliazzo and Avi Wigderson (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

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

बीपीपी (जटिलता)

Namespaces

More

Page actions

Contents

परिभाषा

समस्याएँ

संबंधित वर्ग

जटिलता-सैद्धांतिक गुण

समापन गुण

सापेक्षीकरण

व्युत्पन्नकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बीपीपी (जटिलता)

परिभाषा

समस्याएँ

संबंधित वर्ग

जटिलता-सैद्धांतिक गुण

समापन गुण

सापेक्षीकरण

व्युत्पन्नकरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories