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