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