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

נוספו 303 בתים ,  לפני 15 שנים
עריכה קלה
(עריכה קלה)
ב[[מדעי המחשב]], '''RP''' (ראשי תיבות של: '''R'''andomized '''P'''olynomial Time.) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומיאלי]] באופן הבא:
# אם הקלט בשפה, האלגוריתם מקבל תמידללא (בהסתברות 1)טעות.
 
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
# אם הקלט בשפה, האלגוריתם מקבל תמיד (בהסתברות 1).
# אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
 
המספר 2/3 אינו מהותי בהגדרה זו, ואפשר להחליפו בכל קבוע גדול מחצי. מחלקת הסיבוכיות המשלימה ל- RP קרויה '''Co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 2/3, ודוחה בוודאות. גם RP וגם המשלימה Co-RPמוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
מחלקת הסיבוכיות המשלימה היא [[Co-RP]].
 
RP ו-[[Co-RP]] מוכלות שתיהן במחלקת הסיבוכיות [[BPP]], שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
 
[[קטגוריה:סיבוכיות]]