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

कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी में, कंप्यूटर विज्ञान की शाखा, बाउंडएड-एरर प्रोबबिलिस्टिक पोलिनोमिअल टाइम (बीपीपी) सभी उदाहरणों के लिए 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]

कोम्प्लेक्सिटी-सैद्धांतिक गुण

अन्य प्रोबबिलिस्टिक कोम्प्लेक्सिटी वर्गों (जेड[[पीपी (कोम्प्लेक्सिटी)]], आरपी (कोम्प्लेक्सिटी), सह-आरपी, बीक्यूपी, पीपी (कोम्प्लेक्सिटी)) के संबंध में बीपीपी, जो पीएसपीएसीई के भीतर पी (कोम्प्लेक्सिटी) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध सख्त है या नहीं।]]

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

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

बीपीपी और एनपी के मध्य संबंध अज्ञात है: यह ज्ञात नहीं है कि बीपीपी एनपी का उपसमुच्चय है या नहीं, एनपी बीपीपी का उपसमुच्चय है या नहीं। यदि एनपी बीपीपी में समाहित है, जिसे असंभावित माना जाता है क्योंकि यह एनपी-पूर्ण समस्याओं के लिए व्यावहारिक समाधान प्रदान करेगा, तो NP = RP और PH ⊆ BPP है।^[4]

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

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

समापन गुण

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

सापेक्षीकरण

दैवज्ञों के संबंध में, हम जानते हैं कि दैवज्ञ ए और बी उपस्थित हैं, जैसे कि P^A = BPP^A और P^B ≠ BPP^B हैं। इसके अतिरिक्त, प्रोबबिलिस्टिकता 1 के साथ यादृच्छिक दैवज्ञ के सापेक्ष, P = BPP और बीपीपी सख्ती से एनपी और सह-एनपी में निहित है।^[6]

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

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

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

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

क्षेत्र के अधिकांश विशेषज्ञों द्वारा कुछ स्थिर छद्म यादृच्छिक संख्या जनरेटरों के अस्तित्व का अनुमान लगाया गया है। इस अनुमान का तात्पर्य है कि यादृच्छिकता पोलिनोमिअल टाइम गणना को अतिरिक्त कम्प्यूटेशनल शक्ति नहीं देती है, अर्थात, 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