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

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