RP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט: מתקן הפניות |
מ שוחזר מעריכות של Matanyabot (שיחה) לעריכה האחרונה של Luckas-bot |
||
| שורה 1: | שורה 1: | ||
ב[[מדעי המחשב]], '''RP''' (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[ |
ב[[מדעי המחשב]], '''RP''' (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] באופן הבא: |
||
# אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2. |
# אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2. |
||
# אם הקלט אינו בשפה, האלגוריתם דוחה. |
# אם הקלט אינו בשפה, האלגוריתם דוחה. |
||
מחלקת הסיבוכיות המשלימה ל- RP קרויה '''Co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה Co-RP מוכלות במחלקת הסיבוכיות [[ |
מחלקת הסיבוכיות המשלימה ל- RP קרויה '''Co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה Co-RP מוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית. |
||
[[קטגוריה:מחלקות סיבוכיות]] |
[[קטגוריה:מחלקות סיבוכיות]] |
||
גרסה מ־16:41, 13 בדצמבר 2010
במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי באופן הבא:
- אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
- אם הקלט אינו בשפה, האלגוריתם דוחה.
מחלקת הסיבוכיות המשלימה ל- RP קרויה Co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה Co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
