RP

במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:

1. אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
2. אם הקלט אינו בשפה, האלגוריתם דוחה.

מחלקת הסיבוכיות המשלימה ל- RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.