ZPP
ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח. בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא ת...
אלגוריתם אקראי
אלגוריתם אקראי הוא תוכנה שמשתמשת במקריות. מקריות = משהו שקורה בלי דפוס, כמו הטלת מטבע. מחלקים את האלגוריתמים האקראיים לשתי קבוצות עיקריות. חוקרים שואלים אם אלגוריתמים אלה יכולים להיות מהירים יותר מאלגוריתמים רגילים. יש שתי קטגוריות חשובות: BPP ו‑P. BPP = בעיות שנפתרות מהר בעזרת מקריות. P = בעיות ש...