RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ robot Adding: ja, ko Modifying: en |
מ robot Adding: sl |
||
שורה 18: | שורה 18: | ||
[[ja:RP]] |
[[ja:RP]] |
||
[[ko:RP]] |
[[ko:RP]] |
||
[[sl:RP]] |
גרסה מ־20:41, 13 באוקטובר 2005
ראשי תיבות של: Randomized Polynomial Time.
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
1. אם הקלט בשפה, האלגוריתם מקבל תמיד (בהסתברות 1).
2. אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
מחלקת הסיבוכיות המשלימה היא Co-RP.
RP ו-Co-RP מוכלות שניהן במחלקת הסיבוכיות BPP, שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.