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

