RP
במדעי המחשב, RP (ראשי תיבות של Randomized Polynomial time) היא מחלקת הסיבוכיות של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי ביחס לגודל הקלט באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
- אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של 1(כלומר - תמיד).
במילים אחרות, האלגוריתם יכול להטיל מטבע בעת ריצתו. המקרה היחידי שבו האלגוריתם מחזיר "כן" הוא אם התשובה היא באמת "כן". לכן, אם האלגוריתם מסיים ועונה "כן", אז התשובה היא בהכרח "כן". עם זאת, האלגוריתם עלול להשיב "לא" וזו תהיה תשובה שגויה.
יש המכנים את המחלקה "R", אך שם זה שגור יותר עבור שפות רקורסיביות.
אם התשובה הנכונה היא "כן" והאלגוריתם מורץ פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות . אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות שקרניים קוסמיות ישבשו את זיכרון המחשב שמריץ את האלגוריתם.[1] מבחינה זו, אם מקור למספרים רנדומליים זמין, רוב האלגוריתמים הרצים במחלקת RP הם מאד פרקטיים.
מחלקת הסיבוכיות המשלימה ל-RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP - אשר גם הבעיות במחלקה הזאת נחשבות פתירות ואלגוריתמיהן נחשבים לפרקטיים, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
אחת השאלות המפורסמות והפתוחות במדעי המחשב נוגעת לדי-רנדומיזציה של אלגוריתמים הסתברותיים עם שגיאה חסומה, כלומר, האם P=RP - ההנחה המקובלת היא שאכן מתקיים השוויון(בניגוד להנחה המקובלת שP וNP לא שווים)
הערות שוליים
- ^ This comparison is attributed to Michael O. Rabin on p. 252 of Gasarch, William (2014), "Classifying Problems into Complexity Classes", in Memon, Atif (ed.), Advances in Computers, Vol. 95 (PDF), Academic Press, pp. 239–292.
מחלקות סיבוכיות חשובות (נוספות) | ||
---|---|---|
נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE |
22444318RP