Двадцять одна задача Карпа
Карп показав, що 21 практична задача — від розфарбування графа до розкладу і пакування — така сама важка, як виконуваність.
Чому це важливо
Результат Кука перестав бути поодиноким і перетворився на карту: стало видно, скільки корисних задач лежить за межею швидкого розв'язання.
Серед задач — комівояжер, вершинне покриття, розбиття на кліки, ранець. Для ШІ це означало, що межа проходить не збоку, а прямо крізь ті задачі, які поле намагалося розв'язувати. Саме після цього евристичний пошук, наближені методи й обмежені предметні області стали не компромісом, а єдиною відповіддю.