PP

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

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

x \in L \quad \Rightarrow\quad \Pr[M(x) = ACCEPT] \ge \frac12

x \not\in L \quad\Rightarrow\quad \Pr[M(x) = ACCEPT] < \frac12


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

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

המחלקה הוגדרה לראשונה על ידי גיל ב-1975 [1]

הגדרה חלופית[עריכת קוד מקור | עריכה]

אפשר להגדיר את המחלקה הזו באופן חלופי , נאמר ש- L\in PP אם יש מ"ט אי דטרמינסטית כך שלכל x אם הוא שייך לשפה L אזי לפחות חצי ממסלולי החישוב מקבלים אפשר להגדיל את מסלולי החישוב המקבלים שרירותית (עד כדי אקספוננציאלי) . כלומר : \mbox{PP}=\{ \exists \mbox{NTM} \  M , x \in L \iff \# acc_M (x) > 2^{p(n)-1} \}

תכונות[עריכת קוד מקור | עריכה]

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

קשר עם מחלקות אחרות[עריכת קוד מקור | עריכה]

אפשר להגיד מיידית כי BPP מוכלת ב- PP וזאת מההגדרה , ומכאן ברור גם כי P גם כן שייכת למחלקה PP , אפשר להוכיח בקלות כי NP שייכת ל- PP וזה נובע מכך שאפשר להראות כי SAT שייכת ל- PP אפשר לבנות מ"ט הסתברותית שתעשה זאת על ידי בחירה אקראית של השמה ואז אם הנוסחה ספיקה אז נקבל אחרת נדחה בהסתברות \frac 12 . מאחר ש- PP סגורה למשלים אז גם co-NP שייכת ל- PP . אפשר להראות תוצאה עוד יותר חזקה ולהראות כי MA שייכת ל- PP , המחלקה MA היא מחלקת כל השפות שיש להן פרוטוקול מרלין-ארתור וזאת יש מההגדרה ישירות . הדבר שהוא קצת מפתיע שאפשר להראות כי המחלקה BQP שייכת ל- PP כאשר BQP היא מחלקת השפות שאפשר לקבל אותן על ידי מ"ט קוונטית . בנוסף מתקיים PP^{BQP}=PP כלומר PQB נמוכה (Low) ל- PP . אחד המשפטים החשובים ביותר בסיבוכיות הוא משפט תודה שמראה שההרככיה הפולינומית PH ניתנת לעשות ממנה רדוקציה טיורנג דיטרמניסטית למחלקה PP כלומר PH \subseteq P^{PP} , בנוסף אלינדר הראה כי TC0 ⊂ PP כלומר TC0 היא תת-קבוצה ממש של PP , ברור כי PP שייכת ל-EXP אבל אפשר לשפר זאת ל- PSPACE על ידי כך שמראים כי הבעיה MAJSAT שהיא בעיה שלמה למחלקה PP שייכת ל- PSPACE .

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

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

מקורות[עריכת קוד מקור | עריכה]

  1. ^ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977