לדלג לתוכן

RP – הבדלי גרסאות

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