קבוצה בלתי תלויה (תורת הגרפים)
קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו. אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו. סימול נפוץ לגודל הגדול ביותר הוא α של הגרף. השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהי...
בעיית התפוצצות מצבים
התפוצצות קומבינטורית היא כשמשהו גדל מאוד מהר. קומבינטורית קשורה לספירה ולסידור של דברים. דוגמאות קצרות: פונקציית העצרת. העצרת מחשבת את המכפלה של כל המספרים מ‑1 ועד מספר נתון. יש גם פונקציית אקרמן. בתוכנה יש 'התפוצצות מצבים'. זה כשיש המון דרכים שהתוכנה יכולה לפעול בהן. גם תוספת קטנה של קלט יכולה לי...