RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
fix en, ko remove ja, sl |
הגהונת; הסרת קטגוריה:מדעי המחשב |
||
שורה 2:
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
▲2. אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
מחלקת הסיבוכיות המשלימה היא [[Co-RP]].
שורה 12 ⟵ 9:
RP ו-[[Co-RP]] מוכלות שניהן במחלקת הסיבוכיות [[BPP]], שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
[[קטגוריה:סיבוכיות]]
| |||