RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Luckas-bot (שיחה | תרומות) מ r2.7.1) (בוט מוסיף: vi:RP (độ phức tạp) |
מ r2.7.2) (בוט מוסיף: fr:RP (complexité) |
||
| שורה 11: | שורה 11: | ||
[[de:RP (Komplexitätsklasse)]] |
[[de:RP (Komplexitätsklasse)]] |
||
[[eo:RP (komplikeco)]] |
[[eo:RP (komplikeco)]] |
||
[[fr:RP (complexité)]] |
|||
[[ja:RP (計算複雑性理論)]] |
[[ja:RP (計算複雑性理論)]] |
||
[[ko:RP (복잡도)]] |
[[ko:RP (복잡도)]] |
||
גרסה מ־00:54, 15 בינואר 2013
במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
- אם הקלט אינו בשפה, האלגוריתם דוחה.
מחלקת הסיבוכיות המשלימה ל- RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
