RP – הבדלי גרסאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
YurikBot (שיחה | תרומות)
מ robot Adding: ja, ko Modifying: en
RobotJcb (שיחה | תרומות)
מ 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, שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.