RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט: שינויים קוסמטיים |
Luckas-bot (שיחה | תרומות) מ r2.7.1) (בוט מוסיף: vi:RP (độ phức tạp) |
||
שורה 13: | שורה 13: | ||
[[ja:RP (計算複雑性理論)]] |
[[ja:RP (計算複雑性理論)]] |
||
[[ko:RP (복잡도)]] |
[[ko:RP (복잡도)]] |
||
[[vi:RP (độ phức tạp)]] |
|||
[[zh:RP (複雜度)]] |
[[zh:RP (複雜度)]] |
גרסה מ־07:42, 2 במרץ 2012
במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
- אם הקלט אינו בשפה, האלגוריתם דוחה.
מחלקת הסיבוכיות המשלימה ל- RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.