RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
| שורה 1: | שורה 1: | ||
ראשי תיבות של: '''R'''andomized, '''P'''olynomial Time. |
|||
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא: |
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא: |
||
גרסה מ־20:36, 28 ביוני 2005
ראשי תיבות של: Randomized, Polynomial Time.
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
1. אם הקלט בשפה, האלגוריתם מקבל תמיד (בהסתברות 1).
2. אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
מחלקת הסיבוכיות המשלימה היא Co-RP.
RP ו-Co-RP מוכלות שניהן במחלקת הסיבוכיות BPP, שמכילה את כל הבעיות הניתנות להכרעה הסתברותית ים שגיאה דו-צדדית.