PP

במדעי המחשב ובתורת הסיבוכיות, PP, היא ראשי תיבות של Probabilistic Polynomial Time, היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי כאשר האלגוריתם מחזיר תשובה נכונה בהסתברות שגדולה ממש מ-1/2. באופן פורמלי, שפה $L$ שייכת לPP אם קיימת מכונת טיורינג הסתברותית כל שעבור כל מילת קלט $x$, המכונה רצה זמן פולינומי, ומחזירה פלט (ACCEPT/REJECT) כך שמתקיים

$x \in L \quad \Rightarrow\quad \Pr[M(x) = ACCEPT] \ge \frac12$

$x \not\in L \quad\Rightarrow\quad \Pr[M(x) = ACCEPT] < \frac12$

המחלקה PP סגורה למשלים (על פי הגדרתה). בניגוד למחלקות RP ,BPP ,Co-RP לא ניתן לבצע הגברה לכל הבעיות ב-PP.

PP מכילה את RP ,BPP ,Co-RP.

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.