RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
עריכה קלה |
||
| שורה 1: | שורה 1: | ||
ראשי תיבות של: '''R'''andomized '''P'''olynomial Time |
ב[[מדעי המחשב]], '''RP''' (ראשי תיבות של: '''R'''andomized '''P'''olynomial Time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומיאלי]] באופן הבא: |
||
| ⚫ | |||
RP היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא: |
|||
| ⚫ | |||
# אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3. |
# אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3. |
||
המספר 2/3 אינו מהותי בהגדרה זו, ואפשר להחליפו בכל קבוע גדול מחצי. מחלקת הסיבוכיות המשלימה ל- RP קרויה '''Co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 2/3, ודוחה בוודאות. גם RP וגם המשלימה Co-RPמוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית. |
|||
מחלקת הסיבוכיות המשלימה היא [[Co-RP]]. |
|||
RP ו-[[Co-RP]] מוכלות שתיהן במחלקת הסיבוכיות [[BPP]], שמכילה את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית. |
|||
[[קטגוריה:סיבוכיות]] |
[[קטגוריה:סיבוכיות]] |
||
גרסה מ־19:52, 27 באפריל 2006
במדעי המחשב, RP (ראשי תיבות של: Randomized Polynomial Time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומיאלי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל ללא טעות.
- אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.
המספר 2/3 אינו מהותי בהגדרה זו, ואפשר להחליפו בכל קבוע גדול מחצי. מחלקת הסיבוכיות המשלימה ל- RP קרויה Co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 2/3, ודוחה בוודאות. גם RP וגם המשלימה Co-RPמוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.