לדלג לתוכן

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

נוספו 13 בתים ,  לפני 6 שנים
מ
בוט החלפות: {{הערות שוליים}}
אין תקציר עריכה
מ (בוט החלפות: {{הערות שוליים}})
אם התשובה הנכונה היא "כן" והאלגוריתם מורץ 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]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
{{קצרמר|מחשבים}}