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

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

في نظرية التعقيد الحسابي القسم 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