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