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

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

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

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

تعريف[عدل]

  •  L\in \mathcal{PP} إذا يوجد آلة تيورنج احتمالية ، M ، حيث يتحقق :
 \mbox{Pr}[M(x)=\chi _L(x)] > \frac 12

حيث أنَّ  
\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 23

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

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

 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}p1 ، فلننظر إلى الزوج  (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[2]
  • PPBQP=PP
  • PH⊆PPP=P#P هذه النتيجة تُسمى مبرهنة تودا[3]
  • TC0 ⊂PP [4]
  • PP⊆ PSPACE ، حتى نبين هذا علينا أن نبرهن أنَّ MAJSAT تتبع القسم PSPACE وهذا سهل للغاية بما أننا يمكننا أن نحاكي كل مسارات الحساب في الة تيورنج غير قطعية كثيرة الحدود بواسطة مساحة متعددة الحدود .
  • (k , ∃ L∈{0,1}* : L∈PP ∧ L∉SIZE(n^k ∀ هذه النتيجة نابعة من مبرهنة كارب ليبتون . [5]
  • PostBQP=PP ,
  • PQP=PP ,

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

مراجع[عدل]

  1. ^ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
  2. ^ L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.
  3. ^ S. TODA: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991.
  4. ^ Allender, E. (1996), A note on uniform circuit lower bounds for the counting hierarchy, “Proceedings 2nd International Computing and Combinatorics Conference (COCOON)”, Springer Lecture Notes in Computer Science 1090: 127–135
  5. ^ N. V. Vinodchandran, A note on the circuit complexity of PP