לדלג לתוכן

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

אין שינוי בגודל ,  לפני 14 שנים
אין תקציר עריכה
אין תקציר עריכה
אין תקציר עריכה
ב[[מדעי המחשב]], '''RP''' (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] באופן הבא:
# אם הקלט אינו בשפה, האלגוריתם דוחהמקבל ללא טעות.
# אם הקלט אינו בשפה, האלגוריתם מקבלדוחה בהסתברות של לפחות 1/2/3.
 
מחלקת הסיבוכיות המשלימה ל- RP קרויה '''Co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה Co-RPמוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
משתמש אלמוני