הצגת המקור של הדף "PP (מחלקת סיבוכיות)"

ב[[מדעי המחשב]] וב[[תורת הסיבוכיות]], '''PP''', (ראשי תיבות של Probabilistic Polynomial Time), היא [[מחלקת סיבוכיות|מחלקת הסיבוכיות]] של הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] כאשר ה[[אלגוריתם]] מחזיר תשובה נכונה בהסתברות שגדולה ממש מ-1/2. באופן פורמלי, [[שפה פורמלית|שפה]] <math>L</math> שייכת ל־PP אם קיימת [[מכונת טיורינג הסתברותית]] כך שעבור כל מילת [[קלט]] <math>x</math>, המכונה רצה זמן פולינומי, ומחזירה [[פלט]] (ACCEPT/REJECT) כך שמתקיים 
<div style="text-align: center;">
<math>x \in L \quad \Rightarrow\quad \Pr[M(x) = ACCEPT] > \frac12</math>

<math>x \not\in L \quad\Rightarrow\quad \Pr[M(x) = ACCEPT] \le \frac12</math>
</div>

PP מכילה את [[RP]] ,[[BPP]] ,[[Co-RP]] וגם את NP (ראו פירוט למטה). 
המחלקה הוגדרה לראשונה על ידי ג'ון גיל ב-1975{{הערה|1=  J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977}}

==תכונות==

בניגוד למחלקות [[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 סגור לאיחוד וחיתוך).

==קשר עם מחלקות אחרות==
ידוע כי BPP מוכלת ב- PP וזאת מההגדרה, ומכאן ברור גם כי P גם כן שייכת למחלקה PP. אפשר להוכיח כי NP מוכלת ב-PP על ידי כך שמראים כי SAT שייכת ל-PP: אפשר לבנות [[מכונת טיורינג]] הסתברותית שתעשה זאת על ידי בחירה אקראית של השמה; אם הנוסחה מסופקת המכונה מקבלת ואם לא היא דוחה בהסתברות <math>\frac 12 </math>. מאחר ש-PP סגורה למשלים אז גם co-NP שייכת ל-PP. אפשר להראות תוצאה חזקה יותר,  MA שייכת ל- PP. המחלקה MA היא מחלקת כל השפות שיש להן [[מערכת הוכחה אינטראקטיבית#פרוטוקול ארתור-מרלין|פרוטוקול מרלין-ארתור]] וזה נובע ישירות מההגדרה.

עובדה מפתיעה יותר היא שאפשר להראות כי המחלקה [[BQP]] מוכלת ב-PP, כאשר BQP היא מחלקת השפות שאפשר לקבל אותן על ידי [[מחשב קוונטי|מכונת טיורינג קוונטית]]. בנוסף מתקיים <math>PP^{BQP}=PP</math> כלומר PQB נמוכה (Low) ל- PP. 

כדי להבין את הכוח של המחלקה PP חוקרים לעיתים את המחלקה  <math>P^{PP}</math>, כלומר [[P (סיבוכיות)|P]] מצוידת עם [[אורקל (מדעי המחשב)|אורקל]] של PP. ידוע כי <math>P^{PP} = P^{\#P}</math> כש-[[P#]]  היא מחלקת הסיבוכיות המכילה את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה NP. אחד המשפטים החשובים ביותר בסיבוכיות הוא [[משפט טודה]] שמראה כי ניתן לעשות רדוקציה פולינומית דטרמיניסטית מ[[ההיררכיה הפולינומית]] PH ל-PP, כלומר <math>PH \subseteq P^{PP} </math>.

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

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

ב-2005 הראה ארונסון כי PostBQP (הרחבה של המחלקה [[BQP]] כך שאפשר לעשות [[הסתברות מותנית|התניה]] על הופעת [[קיוביט|קיוביטים]]) שווה ל-PP ובנוסף PP שווה למחלקה PQP שהיא הרחבה של BQP כך שהטעות לא מוגבלת{{הערה|[http://rspa.royalsocietypublishing.org/content/461/2063/3473 Quantum computing, postselection, and probabilistic polynomial-time]}}.

==הערות שוליים==
{{הערות שוליים}}

{{מחלקות סיבוכיות}}
[[קטגוריה:מחלקות סיבוכיות]]