הצגת המקור של הדף "RP"

ב[[מדעי המחשב]], '''RP''' ([[ראשי תיבות]] של Randomized Polynomial time) היא [[מחלקת סיבוכיות|מחלקת הסיבוכיות]] של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] ביחס לגודל ה[[קלט]] באופן הבא:
# אם הקלט בשפה, ה[[אלגוריתם]] מקבל בהסתברות של לפחות 1/2.
# אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של 1(כלומר - תמיד).

במילים אחרות, האלגוריתם יכול [[הטלת מטבע|להטיל מטבע]] בעת ריצתו. המקרה היחידי שבו האלגוריתם מחזיר "כן" הוא אם התשובה היא באמת "כן". לכן, אם האלגוריתם מסיים ועונה "כן", אז התשובה היא בהכרח "כן". עם זאת, האלגוריתם עלול להשיב "לא" וזו תהיה תשובה שגויה.

יש המכנים את המחלקה "R", אך שם זה שמור יותר עבור שפות רקורסיביות.

אם התשובה הנכונה היא "כן" והאלגוריתם מורץ <math>n</math> פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות <math>1-2^{-n}</math>. אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות ש[[קרינה קוסמית|קרניים קוסמיות]] ישבשו את [[זיכרון גישה אקראית|זיכרון המחשב]] שמריץ את האלגוריתם.{{הערה|This comparison is attributed to [[Michael O. Rabin]] on p. 252 of {{citation|contribution=Classifying Problems into Complexity Classes|first=William|last=Gasarch|url=http://www.cs.umd.edu/~gasarch/COURSES/452/F14/mysurvey.pdf|pages=239–292| author1-link=William Gasarch | title=Advances in Computers, Vol. 95|editor-first=Atif|editor-last=Memon|publisher=Academic Press|year=2014}}.}} מבחינה זו, אם [[מחולל מספרים אקראיים|מקור למספרים רנדומליים]] זמין, רוב האלגוריתמים הרצים במחלקת RP הם מאוד פרקטיים.

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

אחת השאלות המפורסמות והפתוחות במדעי המחשב נוגעת לדי-רנדומיזציה של אלגוריתמים הסתברותיים עם שגיאה חסומה, כלומר, האם P=RP - ההנחה המקובלת היא שאכן מתקיים השוויון (בניגוד להנחה המקובלת שP וNP לא שווים)

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{מחלקות סיבוכיות}}
{{קצרמר|מחשבים}}

[[קטגוריה:מחלקות סיבוכיות]]