Введение
Булева выполнимость является NP-полной задачей, и поэтому существуют NP-полные проблемы. В теории вычислительной сложности теорема Кука — Левина, также известная как теорема Кука, утверждает, что проблема булевой выполнимости является NP-полной. То есть, она принадлежит классу NP, и любая задача из NP может быть сведена в полиномиальное время детерминированной машиной Тьюринга к проблеме булевой выполнимости. Теорема названа в честь Стивена Кука и Леонида Левина. Доказательство было предложено Ричардом Карпом, основанное на более раннем доказательстве (использующем иное понятие сведения) Стивена Кука, представленном в материалах недавно основанного симпозиума ACM по теории вычислений. В последующей статье Ричарда Карпа «Сводимость среди комбинаторных задач»…
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin. The proof is due to Richard Karp, based on an earlier proof (using a different notion of reducibility) by Cook. in conference proceedings of the newly founded ACM Symposium on Theory of Computing. Richard Karp's subsequent paper, "Reducibility among
combinatorial problems",
Теоретический интерес к NP-полноте также был усилен работами Теодора П. Бейкера, Джона Гилла и Роберта Соловая, которые в 1975 году показали, что решение NP-задач в определенных моделях оракульных машин требует экспоненциального времени. То есть, существует оракул A, такой, что для всех субекспоненциальных классов детерминированной временной сложности T, релятивизированный класс сложности NPA не является подмножеством TA. В частности, для этого оракула PA ≠ NPA. В СССР результат, эквивалентный результатам Бейкера, Гилла и Соловая, был опубликован в 1969 году М. Дехтиаром. Позже статья Леонида Левина «Универсальные задачи поиска» была опубликована в 1973 году, хотя о ней упоминалось в докладах и она была представлена для публикации за несколько лет до этого. Подход Левина несколько отличался от подхода Кука и Карпа тем, что он рассматривал задачи поиска, требующие нахождения решений, а не просто определения их существования. Он представил шесть таких NP-полных задач поиска, или универсальных задач. Кроме того, он нашёл для каждой из этих задач алгоритм, решающий её за оптимальное время (в частности, эти алгоритмы работают за полиномиальное время тогда и только тогда, когда P = NP).
The theoretical interest in NP completeness was also enhanced by the work of Theodore P. Baker, John Gill, and Robert Solovay who showed, in 1975, that solving NP problems in certain oracle machine models requires exponential time. That is, there exists an oracle A such that, for all subexponential deterministic time complexity classes T, the relativized complexity class NPA is not a subset of TA. In particular, for this oracle, PA ≠ NPA. In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar. Later Leonid Levin's paper, "Universal search problems", was published in 1973, although it was mentioned in talks and submitted for publication a few years earlier. Levin's approach was slightly different from Cook's and Karp's in that he considered search problems, which require finding solutions rather than simply determining existence. He provided six such NP complete search problems, or universal problems. Additionally he found for each of these problems an algorithm that solves it in optimal time (in particular, these algorithms run in polynomial time if and only if P = NP).
Определения
Задача принятия решения находится в классе NP, если она может быть решена недетерминированной машиной Тьюринга за полиномиальное время. Экземпляр задачи булевой выполнимости – это булево выражение, составленное из булевых переменных с помощью булевых операторов. Такое выражение является выполнимым, если существует такая подстановка значений истинности переменным, при которой всё выражение становится истинным.
Идея
Для любой задачи принятия решений из класса NP постройте недетерминированную машину, которая решает её за полиномиальное время. Затем, для каждого входа этой машины, постройте булево выражение, которое определяет, правильно ли машина работает с этим конкретным входом, останавливается ли она и выдаёт ли ответ "да". Это выражение выполнимо тогда и только тогда, когда существует способ, при котором машина работает правильно и выдаёт ответ "да". Следовательно, выполнимость построенного выражения эквивалентна вопросу о том, выдаст ли машина ответ "да".
Сложность
В то время как описанный выше метод кодирует недетерминированную машину Тьюринга с точки зрения сложности, в литературе описаны более сложные подходы к изучению сложности. Квазилинейный результат впервые был получен через семь лет после оригинальной публикации Кука. Применение SAT для доказательства существования NP-полной задачи можно расширить на другие вычислительные задачи в логике, а также на полноту для других классов сложности. Задача о квантованных булевых формулах (QBF) включает булевы формулы, расширенные вложенными универсальными и экзистенциальными кванторами для своих переменных. Задача QBF может быть использована для кодирования вычислений с помощью машины Тьюринга, ограниченной полиномиальной сложностью по пространству, что доказывает существование задачи (распознавания истинных квантованных булевых формул), являющейся PSPACE-полной. Аналогично, формулы с квантованными зависимостями кодируют вычисления с помощью машины Тьюринга, ограниченной логарифмической сложностью по пространству, доказывая существование задачи, являющейся NL-полной.
Последствия
Доказательство показывает, что каждая задача из NP может быть сведена в полиномиальное время (фактически, достаточно логарифмического пространства) к экземпляру задачи булевой выполнимости. Это означает, что если бы задачу булевой выполнимости можно было решить за полиномиальное время детерминированной машиной Тьюринга, то все задачи из NP можно было бы решить за полиномиальное время, и, следовательно, класс сложности NP был бы равен классу сложности P.
Значение NP-полноты стало очевидным после публикации в 1972 году основополагающей работы Ричарда Карпа «Сводимость между комбинаторными задачами», в которой он показал, что 21 разнообразная комбинаторная и теоретико-графовая задача, каждая из которых печально известна своей вычислительной сложностью, является NP-полной. Карп доказал NP-полноту каждой из этих задач, сводя к ней другую задачу (уже доказанную NP-полной). Например, он показал, что задача 3SAT (задача булевой выполнимости для выражений в конъюнктивной нормальной форме (КНФ) с ровно тремя переменными или отрицаниями переменных в каждом дизъюнкте) является NP-полной, показав, как свести (за полиномиальное время) любой экземпляр SAT к эквивалентному экземпляру 3SAT. Грей и Джонсон представили более 300 NP-полных задач в своей книге «Компьютеры и неразрешимость: руководство по теории NP-полноты», и новые задачи продолжают обнаруживаться, принадлежащие к этому классу сложности. Хотя многие практические экземпляры SAT могут быть решены эвристическими методами, вопрос о существовании детерминированного полиномиального алгоритма для SAT (и, следовательно, для всех остальных NP-полных задач) остается известной нерешенной проблемой, несмотря на десятилетия интенсивных усилий специалистов по вычислительной сложности, математических логиков и других исследователей. Более подробную информацию можно найти в статье «Проблема P против NP».