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

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

BPP algorithm (1 run)
Answer produced Correct answer	Yes	No
Yes	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3
BPP algorithm (k runs)
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 'BPP' में है यदि और केवल तभी जब कोई संभाव्य ट्यूरिंग मशीन M मौजूद हो, जैसे कि

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

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

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

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^-सी तरफ, या 2 जैसी छोटी त्रुटि की आवश्यकता है^{-n^{दूसरी ओर, c}} जहां c कोई धनात्मक स्थिरांक है, और n इनपुट की लंबाई है। त्रुटि संभावना की पसंद में यह लचीलापन त्रुटि-प्रवण एल्गोरिदम को कई बार चलाने और अधिक सटीक एल्गोरिदम प्राप्त करने के लिए रन के बहुमत परिणाम का उपयोग करने के विचार पर आधारित है। संभावना है कि अधिकांश रन चेर्नॉफ़ बाध्य के परिणामस्वरूप गलत घातीय क्षय हैं।^[1]

समस्याएँ

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

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

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

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

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

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

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

यह ज्ञात है कि BPP पूरक (जटिलता) के अंतर्गत बंद है; अर्थात्, BPP = सह-BPP। 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) के लिए, कोई सापेक्ष ई गणना में उत्तरों को विशेष गैर-उत्तर में ठीक कर देगा, इस प्रकार यह सुनिश्चित करेगा कि कोई नकली उत्तर नहीं दिया जाएगा।

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

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

लास्ज़लो बाबई, लांस फ़ोर्टनो, नोआम निसान और एवी विग्डर्सन ने दिखाया कि जब तक EXPTIME MA (जटिलता) तक सीमित नहीं हो जाता, BPP इसमें समाहित है^[8] : ${\textsf {i.o.-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {i.o.-DTIME}}\left(2^{n^{\varepsilon }}\right).$ वर्ग i.o.-SUBEXP, जिसका अर्थ अनंत बार SUBEXP है, में ऐसी समस्याएं हैं जिनमें अनंत रूप से कई इनपुट आकारों के लिए उप-घातांकीय समय एल्गोरिदम हैं। उन्होंने यह भी दिखाया कि यदि घातीय-समय पदानुक्रम है तो पी = बीपीपी, जिसे बहुपद पदानुक्रम और ई के रूप में ई के रूप में परिभाषित किया गया है।^PH, E तक ढह जाता है; हालाँकि, ध्यान दें कि घातीय-समय पदानुक्रम को आमतौर पर ढहने के लिए नहीं होने का अनुमान लगाया जाता है।

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

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

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

यह भी देखें

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

संदर्भ

↑ 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