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

