بي بي (تعقيد حسابي)

في نظرية التعقيد الحسابي القسم PP هو قسم لالات تيورنج الاحتمالية التي تخطأ على كل المدخلات باحتمال ${\frac {1}{2}}$ .

الكلمة PP هي اختصار للكلمتين probabilistic polynomial , قسم التعقيد هذا عرفه غيل عام 1977.

تعريف

• $L\in {\mathcal {PP}}$ إذا يوجد آلة تيورنج احتمالية، M ، حيث يتحقق:

${\mbox{Pr}}[M(x)=\chi _{L}(x)]>{\frac {1}{2}}$

حيث أنَّ $\chi _{L}(x)={\begin{cases}1&{\mbox{if }}x\in L\\0&{\mbox{otherwise}}\end{cases}}$

• تعريف آخر لهذا القسم هو أنه قسم الآلات تيورنج غير قطعية حيث أنَّ أغلبية (أكثر من النصف) مسارات الحساب موافقة (أي جوابها «نعم»), أي: ${\mbox{PP}}=\{\exists {\mbox{NTM}}\ M,x\in L\iff \#acc_{M}(x)>2^{p(n)-1}\}$

مسائل كاملة

بخلاف أقسام احتمالية أخرى لهذا القسم يوجد مسائل كاملة، ونعني بالمسائل الكاملة أنها تابعة للقسم PP ، كما أن هذه المسائل يمكن اختصار أي مسألة في PP لهذه المسألة بواسطة اختصارات متعددة الحدود، أحد الأمثلة المهمة هي MAJSAT أي مسألة الاكتفاء مع أغلبية (أكثر من النصف) التعويضات في الصيغة، التي هي صيغة على شكل CNF ، قيمتها هي «صحيح» (أو 1).

علاقته مع أقسام أخرى

• BPP⊆PP وهذا لأن الخطأ في الآلات تيورنج التابعة للقسم PP أكبر منه في BPP لذا فان BPP هي مجموعة جزئية ل- PP .
• NP⊆PP , لبيان هذا علينا أن نبين أنَّ مسألة الاكتفاء SAT تابعة للقسم PP ، لذا علينا أن نبني خوارزمية التي تخطأ على كل المدخلات باحتمال أقل من النصف. الخوارزمية جدا بسيطة: لكل متغير اختر بشكل عشوائي 0 أو 1، افحص إذا ما الصيغة مكتفية إذا كانت مكتفية الجواب «نعم» خلاف هذا نختار «نعم» أو «لا» بشكل عشوائي مُوحد. نلاحظ أنه إذا كانت الصيغة غير قابلة للاكتفاء الجواب «نعم» باحتمال 1/2 . لذا هذه الخوارزمية تحقق المطلوب. وبما أن مسألة الاكتفاء NP كاملة أي يمكن اختصار كل مسألة في NP لمسألة الاكتفاء لذا فإن كل مسألة في NP أيضاً تتبع PP .
• coNP⊆PP , بما أنّ PP منغلق للمكمل وبما أنَّ NP مجموعة جزئية ل-PP لذا أيضاً coNP مجموعة جزئية ل- PP.
• MA⊆PP , فلتكن $L\in MA$ لذا يوجد كثير حدود (p(n , ويوجد آلة تيورنج قطعية كثيرة الحدود $Q(x,r,s)$ بحيث يتحقق:

$x\in L\Rightarrow \exists s\in \{0,1\}^{p(n)}Pr[Q(x,r,s)]>{\frac {2}{3}}$

$x\notin L\Rightarrow \forall s\in \{0,1\}^{p(n)}Pr[Q(x,r,s)]<{\frac {1}{3}}$

نأخذ كثير حدود p₁ ونستطيع أن نصغر الخطأ كما نريد. لذا:

$x\in L\Rightarrow \exists s\in \{0,1\}^{p(n)}Pr[Q(x,r,s)]>1-4^{-p(|x|)}$

$x\notin L\Rightarrow \forall s\in \{0,1\}^{p(n)}Pr[Q(x,r,s)]<4^{-p(|x|)}$

في حين أنَّ الاحتمال الموحد مأخوذ في r∈ {0,1}^p₁ ، فلننظر إلى الزوج $(r,s)\in \{0,1\}^{p_{1}(|x|)+p(|x|)}$ ، ويتحقق التالي:

$x\in L\Rightarrow Pr[Q(x,r,s)]>2^{-p(|x|)}(1-4^{-p(|x|)})>4^{-p(|x|)}$

$x\notin L\Rightarrow \forall s\in \{0,1\}^{p(n)}Pr[Q(x,r,s)]<4^{-p(|x|)}$

لذا حسب التعريف L تتبع PP .

• BQP⊆PP
• PP^BQP=PP
• PH⊆P^PP=P^#P هذه النتيجة تُسمى مبرهنة تودا
• TC⁰ ⊂PP
• PP⊆ PSPACE ، حتى نبين هذا علينا أن نبرهن أنَّ MAJSAT تتبع القسم PSPACE وهذا سهل للغاية بما أننا يمكننا أن نحاكي كل مسارات الحساب في آلة تيورنج غير قطعية كثيرة الحدود بواسطة مساحة متعددة الحدود.
• (k , ∃ L∈{0,1}^* : L∈PP ∧ L∉SIZE(n^k ∀ هذه النتيجة نابعة من مبرهنة كارب ليبتون.
• PostBQP=PP ,
• PQP=PP ,

انظر أيضا

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية