BPP

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في علم التعقيد الحسابي قسم التعقيد BPP هو قسم المسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات . اذا اخترنا اي عدد اقل من 1/2 حينها القسم BPP لا يتغير وذلك بطريقة استخدام الخوارزمية عدة مرات .

تعريف[عدل]

  • نقول بأنَّ L∈BPP اذا يوجد آلة تيورنج حتمية كثيرة حدود M ويوجد كثير حدود (r(n ( عدد القطع النقدية التي تستخدمها الالة M ) ويتحقق التالي :

 x\in L \iff Pr_{r' \in_R \{0,1\}^{r(n)}}[M(x,r')=\chi_L(x)]\ge \frac23

حيث أنَّ :  \chi_L(x)=\begin{cases} 
1,  & \mbox{if }x\in L \\
0, & \mbox{if }x\notin L  
\end{cases}

  • فلتكن  T:\mathbb{N} \to \mathbb{N} وكذلك  L \subseteq \{0,1\}^* نقول أنَّ ((L∈BPTIME(T(n اذا يوجد آلة تيورنج احتمالية M وقتها هو (T(n بحيث أنَّها لكل مدخل x\in\{0,1\}^n عدد خطوات حساب M مع المُدخل x هو على الأكثر (|T(|x ومهما كانت اختيارات العشوائية ل- M يتحقق التالي :  Pr[M(x)=\chi_L(x)]\ge \frac23 .

نعرف : \mathcal{BPP}=\cup_{c\ge 0 } BPTIME[n^c]

اقسام على علاقة[عدل]

هنالك عدة اقسام التي هي قريبة من BPP فحذف أحد الشروط او اضافة اخرى يُمَكِن من الحصول على اقسام تعقيد جديدة التي هي ربما تحوي مسائل أكثر , لو منعنا العشوائية في تعريف BPP حينها القسم يكون P . لو استبدلنا آلة تيورنج الاحتمالية بالة تيورنج كمومية القسم الذي نحصل عليه هو BQP . استخدام الخيار المُسبق (POSTSELECTION) مع BPP او السماح لمسارات الحلول ان يختلف طولها حينها نحصل على القسم BPPpath وهذا القسم يحوي NP نظير القسم الاخير الكمومي هو postBQP .

خوارزميات مونتي كارلو هي خوارزميات عشوائية والتي اغلب الوقت تكون صحيحة , BPP هو قسم المسائل التي يوجد لها خوارزميات مونتي كارلو والتي وقتها كثير الحدود .

خصائص نظرية[عدل]

BPP مغلقة تحت المكمل ما معناه أنَّ BPP=co-BPP اي انه اذا سمحنا ل- BPP القوة لحل مسائل فيBPP فهذا لا يعطي \mathcal{BPP} المزيد من القوة اي : BPPBPP=BPP . كما أن BPP مغلق تحت الاتحاد والتقاطع هذا يعني انه لأي مسألتين L_1, L_2 \in \mathcal{\mathcal{BPP}} يتحقق التالي : L_1 \cup L_2, L_1 \cap L_2 \in \mathcal{BPP} .

العلاقة بين BPP و-NP غير معروفة اي ليس معلوما اذا ما BPP⊆NP او العكس . واذا فرضنا ان NP⊆BPP , وهذه الفرضية غير مُحتملة لانها تعني انَّ المسائل في NP كاملة يوجد لها حل عملي, يتحقق NP=RP , وأيضا PH⊆BPP .

كما انه معلوم أنَّ RP⊆BPP⊆PP ولا يُعلم اذا أحد من هذه الاحتواءات هو فعلي (Proper) واذا ما عُلم ان احدها فعلي فان هذا يعني PSPACE≠P

نظرية سبسر لوتمان والتي نصها بانَّ \mathcal{BPP}\subseteq \Sigma_2 \cap \Pi_2 \subseteq PH اي انه في حال أن NP=P حينها  \mathcal{BPP}=P=PH .

نظرية ادليمان التي تنص على أن  \mathcal{BPP} \subseteq \mbox{P/Poly} واحد تبعات هذه النظرية هو انه يمكن فك العشوائية لخوارزميات في BPP لتكون خوارزميات قطعية بمساعدة سلسلة عشوائية واحدة . بالرغم من هذا قد يتطلب ايجاد هذه السلسلة الكثير من الوقت .

انظر أيضا[عدل]