משפט קוק-לוין

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