הבדלים בין גרסאות בדף "PP"

נוספו 47 בתים ,  לפני 4 שנים
אין תקציר עריכה
 
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 סגור לאיחוד וחיתוך).
1,197

עריכות