Теорема Кука
Кук показав, що задача виконуваності булевої формули — найважча у своєму класі: до неї зводиться будь-яка задача, розв'язок якої можна швидко перевірити.
Чому це важливо
З'явилася межа між «можна перевірити» і «можна знайти» — питання, яке досі визначає, що від машини взагалі варто вимагати.
Робота вводить поняття, яке згодом назвали NP-повнотою, і ставить питання P проти NP. Для ШІ це не абстракція: пошук у просторі станів, виконання обмежень і виведення в логіці першого порядку — усе це задачі тієї самої природи. Евристики потрібні не тому, що алгоритми недосконалі, а тому, що точний перебір нездійсненний у принципі.