RP – הבדלי גרסאות

הוסרו 11 בתים ,  לפני 15 שנים
שיפוץ
(עריכה קלה)
(שיפוץ)
ב[[מדעי המחשב]], '''RP''' (ראשי תיבותהתיבות של: '''R'''andomizedRandomized '''P'''olynomialPolynomial Timetime) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומיאלי]] באופן הבא:
# אם הקלט בשפה, האלגוריתם מקבל ללא טעות.
# אם הקלט אינו בשפה, האלגוריתם דוחה בהסתברות של לפחות 2/3.