PP

מתוך ויקיפדיה, האנציקלופדיה החופשית

ראשי תיבות של Probabilistic Polynomial Time.

PP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי כאשר האלגוריתם מחזיר תשובה נכונה בהסתברות שגדולה ממש מ-1/2.

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

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

שפות אחרות