RP

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

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

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