BPP (מחלקת סיבוכיות)
BPP היא קבוצה של בעיות שמחשב יכול לפתור בעזרת ריצות שרצות בהגרלה. אלגוריתם אקראי (אלגוריתם שמשתמש בהגרלות) עונה נכון בדרך כלל. אם יש אלגוריתם שמריץ את עצמו במהירות סבירה (זמן פולינומי, זמן שמגדל לאט יחסית), והוא נותן את התשובה הנכונה ברוב ההרצות, אז הבעיה ב‑BPP. בדרך כלל "ברוב" משתמע כ‑2 מתוך 3 פע...
מטריצות פאולי
מטריצות פאולי הן שלוש "טבלאות" קטנות של מספרים. כל טבלה היא בגודל שני על שני. "טבלה" כאן פירושה מטריצה. יש שלוש מטריצות: σ1, σ2 ו‑σ3. כל אחת נותנת דרך שונה לשנות וקטור קטן של שני מספרים. אחת מחליפה בין שתי הכניסות. השנייה משתמשת ב‑i, שהוא מספר דמיוני. השלישית נותקת סימן אחד ל־+1 ולחברו ל‑−1. הן מ...