RP

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

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

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

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

אם התשובה הנכונה היא "כן" והאלגוריתם מורץ $n$ פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות $1-2^{-n}$. אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות שקרניים קוסמיות ישבשו את זיכרון המחשב שמריץ את האלגוריתם. מבחינה זו, אם מקור למספרים רנדומליים זמין, רוב האלגוריתמים הרצים במחלקת RP הם מאד פרקטיים.

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

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

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22444318RP