PP (מחלקת סיבוכיות)
PP היא קבוצה של בעיות שמחשבים עם מזל יכולים לפתור בזמן קצר. "מזל" כאן פירושו שהאלגוריתם עושה החלטות אקראיות. האלגוריתם עובד בכמות זמן שמתאימה לגודל הקלט. מחלקת PP אומרת: אם התשובה היא "כן", האלגוריתם צריך להגיד "כן" יותר מחצי מהפעמים. אם התשובה היא "לא", הוא לא אמור להגיד "כן" יותר מחצי מהפעמים. ...
BPP (מחלקת סיבוכיות)
BPP היא קבוצה של בעיות שמחשב יכול לפתור בעזרת ריצות שרצות בהגרלה. אלגוריתם אקראי (אלגוריתם שמשתמש בהגרלות) עונה נכון בדרך כלל. אם יש אלגוריתם שמריץ את עצמו במהירות סבירה (זמן פולינומי, זמן שמגדל לאט יחסית), והוא נותן את התשובה הנכונה ברוב ההרצות, אז הבעיה ב‑BPP. בדרך כלל "ברוב" משתמע כ‑2 מתוך 3 פע...
P (מחלקת סיבוכיות)
P היא קבוצה של בעיות שאפשר לפתור בצורה "מהירה" יחסית. "מהירה" כאן פירושו זמן פולינומי. זמן פולינומי אומר שהזמן גדל בצורה לא מוגזמת כשהקלט גדל. דוגמאות פשוטות ב-P הן חישוב המחלק המשותף הגדול של שני מספרים (GCD) ועץ פורש מינימלי. גם בדיקת האם מספר הוא ראשוני נכנסה ל-P בשנת 2002. בחירת זמן פולינומי ש...
Co-NP
co-NP הוא אוסף בעיות שהן ההפך של הבעיות ב־NP. NP הן בעיות שיש להן הוכחה קצרה שאפשר לבדוק מהר. זמן פולינומי הוא זמן חישוב סביר. דוגמה פשוטה: יש קבוצה של מספרים. שואלים אם יש תת־קבוצה שסכומה אפס. אם כן, נותנים את הרשימה ובודקים את הסכום. ההפך שואל האם אין בכלל תת־קבוצה שסכומה אפס. גם לזה יש הוכחה שני...