# RP

### מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומיאלי באופן הבא:

1. אם הקלט בשפה, האלגוריתם מקבל ללא טעות.
2. אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.

המספר 2/3 אינו מהותי בהגדרה זו, ואפשר להחליפו בכל קבוע גדול מחצי. מחלקת הסיבוכיות המשלימה ל- RP קרויה Co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 2/3, ודוחה בוודאות. גם RP וגם המשלימה Co-RPמוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.

מקור: http://he.wikipedia.org../../../r/p/_/RP_c4cb.html

קטגוריות: סיבוכיות | קצרמר מחשבים

##### Views

- ערך
- שיחה
- גרסה נוכחית

##### קהילה

- שער הקהילה
- עזרה
- דלפק ייעוץ
- מזנון
- יצירת קשר
- ספר אורחים

##### חיפוש

##### שפות אחרות

- English
- Deutsch
- 한국어