RP

במדעי המחשב, RP (ראשי תיבות של Randomized Polynomial time) היא מחלקת סיבוכיות של בעיות שניתנות להכרעה בהסתברות בזמן פולינומי ביחס לגודל הקלט.
האלגוריתם יכול להטיל מטבע או להשתמש במספרים אקראיים במהלך הריצה. אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2. אם הקלט אינו בשפה, האלגוריתם דוחה תמיד.
זה יוצר שגיאה חד‑צדדית: אפשר לטעות רק כשעונים "לא". כאשר מריצים את האלגוריתם n פעמים באופן בלתי תלוי, ההסתברות שלא יתקבל "כן" אף פעם קטנה מ‑2^{-n}. לכן הרצה חוזרת מפחיתה את הסיכון לשגיאה בצורה מעריכית; למשל, 100 הרצות מקטינות את הסיכוי לטעות כמעט לא בטוח.
אם זמין מקור למספרים אקראיים, רוב האלגוריתמים במחלקת RP פרקטיים.
המחלקה המשליםית היא co-RP: אלגוריתם שונה שקולט "כן" תמיד ודוחה "לא" בהסתברות גדולה מ‑1/2. גם RP וגם co-RP מוכלות במחלקת BPP, שמאגדת אלגוריתמים הסתברותיים עם שגיאה דו‑צדדית.
שאלה פתוחה חשובה בתיאוריה היא האם P=RP. הרוב המכריע של החוקרים מניחים שיש שוויון זה. כמו כן, יש שמכנים את המחלקה פשוט R, אך שם זה שמור לשפות רקורסיביות.

RP היא קבוצה של בעיות שמחשב יכול לנסות לפתור במהירות. "Randomized" פירושו שימוש במקריות. "Polynomial time" פירושו זמן סביר יחסית לגודל הבעיה.
האלגוריתם משתמש במקריות. אם התשובה היא "כן", הוא אומר "כן" לפחות בחצי מהפעמים. אם התשובה היא "לא", הוא תמיד אומר "לא".
כך הוא יכול לטעות רק כשאומר "לא". מריצים אותו שוב ושוב כדי להקטין את הטעות. הרצה של הרבה פעמים מקטינה את הסיכוי לטעות מאד.
יש גם co-RP, שהיא ההפך: היא מקבלת "כן" תמיד ועלולה לטעות כשאומרת "לא". שתי הקבוצות האלה בתוך קבוצה גדולה יותר שנקראת BPP.
יש שאלה פתוחה: האם ריצות רגילות ומהירות (P) שוות ל‑RP? רוב החוקרים חושבים שהן שוות.