Теорема Кука — Левина (также просто теорема Кука) утверждает, что задача о выполнимости булевой формулы в КНФ (SAT) является NP-полной.
Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным[1].
В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач распознавания свойств следующим образом. Задача принадлежит классу NP, если:
Этот класс, как позже показал Р. Карп (R. Karp), в свою очередь содержит в себе другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые в пределах этого класса одна к другой.
После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.