RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הגהונת; הסרת קטגוריה:מדעי המחשב |
מ robot Adding: de:RP (Komplexitätsklasse) |
||
| שורה 12: | שורה 12: | ||
[[en:RP (complexity)]] |
[[en:RP (complexity)]] |
||
[[de:RP (Komplexitätsklasse)]] |
|||
[[ko:RP (복잡도)]] |
[[ko:RP (복잡도)]] |
||
גרסה מ־04:59, 16 באפריל 2006
ראשי תיבות של: Randomized Polynomial Time.
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל תמיד (בהסתברות 1).
- אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
מחלקת הסיבוכיות המשלימה היא Co-RP.
RP ו-Co-RP מוכלות שניהן במחלקת הסיבוכיות BPP, שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.