PP (מחלקת סיבוכיות) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תיקון כותרת הערות שוליים שגויה* |
אין תקציר עריכה |
||
שורה 7:
המחלקה PP סגורה למשלים
בניגוד למחלקות [[RP]] ,[[BPP]] ,[[Co-RP]] לא ניתן לבצע הגברה לבעיות ב-PP שכן הטכניקה עצמה תוביל לריצה של האלגוריתם מספר לא פולינומי של פעמים.
PP מכילה את [[RP]] ,[[BPP]] ,[[Co-RP]].▼
▲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}}
| |||