RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ r2.7.2) (בוט מוסיף: fr:RP (complexité) |
Makecat-bot (שיחה | תרומות) מ r2.7.3) (בוט מוסיף: cs:RP (třída složitosti) |
||
| שורה 9: | שורה 9: | ||
[[en:RP (complexity)]] |
[[en:RP (complexity)]] |
||
[[cs:RP (třída složitosti)]] |
|||
[[de:RP (Komplexitätsklasse)]] |
[[de:RP (Komplexitätsklasse)]] |
||
[[eo:RP (komplikeco)]] |
[[eo:RP (komplikeco)]] |
||
גרסה מ־18:29, 22 בינואר 2013
במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
- אם הקלט אינו בשפה, האלגוריתם דוחה.
מחלקת הסיבוכיות המשלימה ל- RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
