https://3rabica.org/index.php?action=history&feed=atom&title=BPPBPP - تاريخ المراجعة2026-06-04T17:23:37Zتاريخ التعديل لهذه الصفحة في الويكيMediaWiki 1.43.7https://3rabica.org/index.php?title=BPP&diff=1649024&oldid=prevعبد العزيز: بوت: إصلاح أخطاء فحص أرابيكا من 1 إلى 1042023-07-08T08:35:44Z<p>بوت: إصلاح أخطاء فحص أرابيكا من 1 إلى 104</p>
<p><b>صفحة جديدة</b></p><div>في علم التعقيد الحسابي قسم التعقيد {{رمز لغة|en|{{اختص|BPP|bounded-error probabilistic polynomial time}}}} هو قسم المسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات.<ref>{{استشهاد ويب| مسار = https://babelnet.org/synset?word=bn:03138635n | عنوان = معلومات عن BPP على موقع babelnet.org | ناشر = babelnet.org| مسار أرشيف = https://web.archive.org/web/20201027002258/https://babelnet.org/synset?word=bn:03138635n | تاريخ أرشيف = 27 أكتوبر 2020 }}</ref> إذا اخترنا أي عدد اقل من 1/2 حينها القسم BPP لا يتغير وذلك بطريقة استخدام الخوارزمية عدة مرات .<br />
== تعريف ==<br />
* نقول بأنَّ L∈BPP إذا يوجد آلة تيورنج حتمية كثيرة حدود M ويوجد كثير حدود (r(n ( عدد القطع النقدية التي تستخدمها الآلة M ) ويتحقق التالي :<br />
<div style="text-align: center;"><br />
<math> x\in L \iff Pr_{r' \in_R \{0,1\}^{r(n)}}[M(x,r')=\chi_L(x)]\ge \frac23 </math><br />
</div><br />
حيث أنَّ : <math> \chi_L(x)=\begin{cases}<br />
1, & \mbox{if }x\in L \\<br />
0, & \mbox{if }x\notin L <br />
\end{cases}</math><br />
* فلتكن <math> T:\mathbb{N} \to \mathbb{N}</math> وكذلك <math> L \subseteq \{0,1\}^* </math> نقول أنَّ ((L∈BPTIME(T(n إذا يوجد آلة تيورنج احتمالية M وقتها هو (T(n بحيث أنَّها لكل مدخل <math>x\in\{0,1\}^n </math> عدد خطوات حساب M مع المُدخل x هو على الأكثر (|T(|x ومهما كانت اختيارات العشوائية ل- M يتحقق التالي : <math> Pr[M(x)=\chi_L(x)]\ge \frac23 </math> .<br />
<br />
نعرف : <math>\mathcal{BPP}=\cup_{c\ge 0 } BPTIME[n^c] </math><br />
<br />
== اقسام على علاقة ==<br />
هنالك عدة اقسام التي هي قريبة من BPP فحذف أحد الشروط أو إضافة أخرى يُمَكِن من الحصول على اقسام تعقيد جديدة التي هي ربما تحوي مسائل أكثر، لو منعنا العشوائية في تعريف BPP حينها القسم يكون P. لو استبدلنا آلة تيورنج الاحتمالية بالة تيورنج كمومية القسم الذي نحصل عليه هو BQP. استخدام [[الخيار المسبق]] (POSTSELECTION) مع BPP أو السماح لمسارات الحلول ان يختلف طولها حينها نحصل على القسم BPP<sub>path</sub> وهذا القسم يحوي NP نظير القسم الاخير الكمومي هو postBQP .<br />
<br />
خوارزميات مونتي كارلو هي خوارزميات عشوائية والتي اغلب الوقت تكون صحيحة , BPP هو قسم المسائل التي يوجد لها خوارزميات مونتي كارلو والتي وقتها كثير الحدود .<br />
<br />
== خصائص نظرية ==<br />
* BPP مغلقة تحت المكمل ما معناه أنَّ BPP=co-BPP أي انه إذا سمحنا ل- BPP القوة لحل مسائل فيBPP فهذا لا يعطي <math>\mathcal{BPP}</math> المزيد من القوة أي : BPP<sup>BPP</sup>=BPP .<br />
* كما أن BPP مغلق تحت الاتحاد والتقاطع هذا يعني انه لأي مسألتين <math>L_1, L_2 \in \mathcal{\mathcal{BPP}}</math> يتحقق التالي :<math> L_1 \cup L_2, L_1 \cap L_2 \in \mathcal{BPP}</math> .<br />
* العلاقة بين BPP و-NP غير معروفة أي ليس معلوما إذا ما BPP⊆NP أو العكس. وإذا فرضنا ان NP⊆BPP , وهذه الفرضية غير مُحتملة لانها تعني انَّ المسائل في NP كاملة يوجد لها حل عملي، يتحقق NP=RP , وأيضا PH⊆BPP .<br />
* كما أنه معلوم أنَّ RP⊆BPP⊆PP ولا يُعلم إذا أحد من هذه الاحتواءات هو فعلي (Proper) وإذا ما عُلم ان أحدها فعلي فان هذا يعني PSPACE≠P<br />
* نظرية سبسر لوتمان والتي نصها بانَّ <math>\mathcal{BPP}\subseteq \Sigma_2 \cap \Pi_2 \subseteq PH </math> أي انه في حال أن NP=P حينها <math> \mathcal{BPP}=P=PH</math> .<br />
* نظرية [[ليونارد أدليمان|ادليمان]] التي تنص على أن <math> \mathcal{BPP} \subseteq \mbox{P/Poly} </math> واحد تبعات هذه النظرية هو انه يمكن فك العشوائية لخوارزميات في BPP لتكون خوارزميات قطعية بمساعدة سلسلة عشوائية واحدة. بالرغم من هذا قد يتطلب إيجاد هذه السلسلة الكثير من الوقت، وهذا معناه : انه لو استطعنا إيجاد هذا «الدليل» بوقت كثير الحدود (أي ان عدد الخطوات في آلة تيورنج محدود بكثير حدود) عندها BPP=P. وبالرغم من هذا لليوم لا يوجد وسيلة معروفة لإيجاده سوى البحث على كل الدلائل وهذا يتطلب وقت أسي ...<br />
<br />
== مراجع ==<br />
{{مراجع}}<br />
<br />
== انظر أيضا ==<br />
* [[قسم تعقيد]]<br />
* [[نظرية التعقيد الحسابي]].<br />
* [[مسألة كثير حدود وكثير حدود غير قطعي|مسألة P=NP]]<br />
* [[خوارزمية]]<br />
{{أقسام تعقيد}}<br />
{{شريط بوابات|رياضيات|علم الحاسوب}}<br />
<br />
[[تصنيف:أقسام التعقيد الحسابي]]<br />
[[تصنيف:معلوماتية نظرية]]</div>عبد العزيز