RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ השוויון(בניגוד->השוויון (בניגוד - תיקון תקלדה בקליק |
Matanyabot (שיחה | תרומות) מ בוט החלפות: |
||
שורה 7:
יש המכנים את המחלקה "R", אך שם זה שגור יותר עבור שפות רקורסיביות.
אם התשובה הנכונה היא "כן" והאלגוריתם מורץ <math>n</math> פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות <math>1-2^{-n}</math>. אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות ש[[קרינה קוסמית|קרניים קוסמיות]] ישבשו את [[זיכרון גישה אקראית|זיכרון המחשב]] שמריץ את האלגוריתם.{{הערה|This comparison is attributed to [[Michael O. Rabin]] on p.
מחלקת הסיבוכיות המשלימה ל-RP קרויה '''co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP [[תת-קבוצה|מוכלות]] במחלקת הסיבוכיות [[BPP]] - אשר גם הבעיות במחלקה הזאת נחשבות פתירות ואלגוריתמיהן נחשבים לפרקטיים, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
|