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

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

समस्याएँ

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 बहुपद की कुल डिग्री है।

संबंधित वर्ग

यदि बीपीपी की परिभाषा से यादृच्छिकता की पहुंच विस्थापित कर दी जाती है, तो हमें जटिलता वर्ग P मिलता है। वर्ग की परिभाषा में, यदि हम साधारण ट्यूरिंग मशीन को क्वांटम कंप्यूटर से प्रतिस्थापित करते हैं, तो हमें वर्ग बीक्यूपी मिलता है।

बीपीपी में पोस्टसेलेक्शन जोड़ने, या गणना पथों को भिन्न-भिन्न लंबाई की अनुमति देने से वर्ग बीपीपी_path मिलता है। बीपीपी_path को एनपी समाहित करने के लिए जाना जाता है, और यह इसके क्वांटम समकक्ष पोस्टबीक्यूपी में निहित है।

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

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

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

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

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

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

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

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

समापन गुण

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

सापेक्षीकरण

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

यहाँ तक कि दैवज्ञ भी है जिसमें BPP=EXP^NP (और इसलिए P<NP<BPP=EXP=NEXP), जिसे निम्नानुसार पुनरावृत्तीय रूप से निर्मित किया जा सकता है। निश्चित 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 है। ध्यान दें कि साधारण जनरेटर इस परिणाम को दिखाने के लिए पर्याप्त नहीं हैं; विशिष्ट यादृच्छिक संख्या जनरेटर का उपयोग करके कार्यान्वित कोई भी संभाव्य एल्गोरिदम मूल के अतिरिक्त कुछ इनपुट पर सदैव त्रुटिपूर्ण परिणाम देगा (चूँकि ये इनपुट दुर्लभ हो सकते हैं)।

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

: