משפט קוק-לוין
משפט קוק-לוין אומר שבעיה בשם SAT היא אחת הקשות בקבוצה שנקראת NP. P הן בעיות שאפשר לפתור מהר. NP הן בעיות שאם נותנים פתרון, אפשר לבדוק מהר אם הוא נכון. שאלה גדולה היא האם כל בעיה שאפשר לבדוק מהר אפשר גם לפתור מהר. זוהי שאלה פתוחה. SAT היא בעיה של נוסחאות לוגיות. נוסחאות אלה כתובות עם משתנים שאפ...
מסלול המילטוני
מסלול המילטוני הוא דרך שעוברת בכל נקודה ברשת בדיוק פעם אחת. רשת כזו נקראת גרף. מעגל המילטוני חוזר לנקודת ההתחלה בסוף. השם בא מויליאם המילטון. הוא המציא משחק ב־1857 שבו יש למצוא מעגל כזה. חידה ידועה אחרת היא מסע הפרש בשחמט. שם פרש צריך לבקר בכל משבצת בדיוק פעם אחת. יש חוקים שמבטיחים שקיים מסלול כזה...