PP (מחלקת סיבוכיות) – הבדלי גרסאות

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

PP סגור ל[[משלים (מתמטיקה)|משלים]], [[חיתוך (מתמטיקה)|חיתוך]] ו[[איחוד (מתמטיקה)|איחוד]]. אפשר לראות מההגדרה ש- PP סגור למשלים כי אפשר להפוך את התשובה של מכונת טיורנג A. דויד רוסו הראה ב-1985 כי PP סגורה להפרש סימטרי. השאלה אם PP סגורה לאיחוד וחיתוך הייתה שאלה פתוחה במשך 14 שנים עד שזו נפתרנפתרה על ידי ביגל, ריינגולד וספילמן{{הערה|R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991, pp. 1–9, 1991.}}. הוכחות חלופיות ניתנו על ידי לי ו[[סקוט ארונסון]] (הוא הראה כי PostBQP=PP ואז הראה הוכחה פשוטה כי PostBQP סגור לאיחוד וחיתוך).