PP (מחלקת סיבוכיות)

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

${\displaystyle x\in L\quad \Rightarrow \quad \Pr[M(x)=ACCEPT]>{\frac {1}{2}}}$

${\displaystyle x\not \in L\quad \Rightarrow \quad \Pr[M(x)=ACCEPT]\leq {\frac {1}{2}}}$

PP מכילה את RP ,BPP ,Co-RP וגם את NP (ראו פירוט למטה). המחלקה הוגדרה לראשונה על ידי ג'ון גיל ב-1975^[1]

תכונות

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

PP סגור למשלים, חיתוך ואיחוד. אפשר לראות מההגדרה ש- PP סגור למשלים כי אפשר להפוך את התשובה של מכונת טיורנג A. דויד רוסו הראה ב-1985 כי PP סגורה להפרש סימטרי. השאלה אם PP סגורה לאיחוד וחיתוך הייתה שאלה פתוחה במשך 14 שנים עד שזו נפתרה על ידי ביגל, ריינגולד וספילמן^[2]. הוכחות חלופיות ניתנו על ידי לי וסקוט ארונסון (הוא הראה כי PostBQP=PP ואז הראה הוכחה פשוטה כי PostBQP סגור לאיחוד וחיתוך).

קשר עם מחלקות אחרות

ידוע כי BPP מוכלת ב- PP וזאת מההגדרה, ומכאן ברור גם כי P גם כן שייכת למחלקה PP. אפשר להוכיח כי NP מוכלת ב-PP על ידי כך שמראים כי SAT שייכת ל-PP: אפשר לבנות מכונת טיורינג הסתברותית שתעשה זאת על ידי בחירה אקראית של השמה; אם הנוסחה מסופקת המכונה מקבלת ואם לא היא דוחה בהסתברות ${\displaystyle {\frac {1}{2}}}$. מאחר ש-PP סגורה למשלים אז גם co-NP שייכת ל-PP. אפשר להראות תוצאה חזקה יותר, MA שייכת ל- PP. המחלקה MA היא מחלקת כל השפות שיש להן פרוטוקול מרלין-ארתור וזה נובע ישירות מההגדרה.

עובדה מפתיעה יותר היא שאפשר להראות כי המחלקה BQP מוכלת ב-PP, כאשר BQP היא מחלקת השפות שאפשר לקבל אותן על ידי מכונת טיורינג קוונטית. בנוסף מתקיים ${\displaystyle PP^{BQP}=PP}$ כלומר PQB נמוכה (Low) ל- PP.

כדי להבין את הכוח של המחלקה PP חוקרים לעיתים את המחלקה ${\displaystyle P^{PP}}$, כלומר P מצוידת עם אורקל של PP. ידוע כי ${\displaystyle P^{PP}=P^{\#P}}$ כש-P# היא מחלקת הסיבוכיות המכילה את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה NP. אחד המשפטים החשובים ביותר בסיבוכיות הוא משפט טודה שמראה כי ניתן לעשות רדוקציה פולינומית דטרמיניסטית מההיררכיה הפולינומית PH ל-PP, כלומר ${\displaystyle PH\subseteq P^{PP}}$.

אריק אלנדר (Allender) הראה כי TC0 ⊂ PP, כלומר TC0, מחלקת השפות הניתנות לזיהוי על ידי מעגלים בוליאניים בעומק קבוע וגודל פולינומי המכילים שערי סף עם מספר לא חסום של קלטים, היא תת-קבוצה ממש של PP. ברור כי PP מוכלת ב-EXP אבל אפשר לחזק זאת ל-PSPACE על ידי כך שמראים כי הבעיה MAJSAT (בהינתן בעיית SAT, האם רוב ההשמות מספקות) שהיא בעיה שלמה למחלקה PP שייכת ל-PSPACE.

אפשר להראות תוצאה דומה למשפט קאנאן (Kannan) למחלקה PP כלומר: (k, ∃ L⊆{0,1}* : L∈PP ∧ L∉SIZE(n^k ∀. טענה זו שונה מהטענה ${\displaystyle PP\nsubseteq P/{\mbox{Poly}}}$ כי לכל k אנו מניחים שיש שפה כזו אבל לא לכל k יש שפה אחת משותפת, כלומר עבור k-ים שונים השפות יכולות להיות שונות.

ב-2005 הראה ארונסון כי PostBQP (הרחבה של המחלקה BQP כך שאפשר לעשות התניה על הופעת קיוביטים) שווה ל-PP ובנוסף PP שווה למחלקה PQP שהיא הרחבה של BQP כך שהטעות לא מוגבלת^[3].