Теорема Кука—Левина

Теорема Кука—Левина утверждает, что задача ВЫПОЛНИМОСТЬ (SAT) является NP-полной. В формулировке курса SAT — распознавание выполнимости булевой КНФ.1, 2

Доказательство состоит из двух частей. Во-первых, для любого языка \(L\in NP\) принимающее вычисление недетерминированной машины за полиномиальное время кодируется КНФ, выполнимой тогда и только тогда, когда исходное слово принадлежит \(L\). Во-вторых, SAT принадлежит \(NP\).1, 2

Что важно запомнить
  • Формулировка: SAT является NP-полной.
  • NP-трудность: любой \(L\in NP\) полиномиально сводится к SAT.1
  • В КНФ кодируются содержимое ячеек ленты, состояние машины и положение головки по шагам вычисления.
  • Ограничения КНФ задают начальную конфигурацию, корректность каждого перехода и наличие принимающего состояния.
  • Вторая часть устанавливает \(SAT\in NP\). Вместе две части дают NP-полноту.2

Формулировка

Теорема Кука—Левина: язык выполнимых КНФ является NP-полным. Эквивалентно, SAT принадлежит \(NP\), и всякий язык \(L\in NP\) полиномиально сводится к SAT.1, 2

Кодирование вычисления КНФ

Пусть НМТ \(M\) распознаёт язык \(L\) за время, ограниченное полиномом \(p(n)\). Для слова \(w\) длины \(n\) рассматривают первые \(T=p(n)\) шагов и первые \(T\) ячеек ленты. Вводятся булевы переменные трёх типов: переменная \(P^i_{s,t}\) сообщает, что в ячейке \(s\) на шаге \(t\) записан символ \(a_i\). Переменная \(Q^j_t\) задаёт состояние \(q_j\). Переменная \(S_{s,t}\) указывает положение головки.1

Затем строится КНФ, выражающая условия корректной таблицы вычисления. Одни группы скобок требуют ровно одного обозреваемого места, одного символа в ячейке и одного состояния. Другие фиксируют начальную конфигурацию. Локальные условия проверяют соответствие переходов программе машины. Заключительная часть требует появления принимающего состояния.

Такая КНФ выполнима тогда и только тогда, когда существует принимающая ветвь вычисления \(M\) на \(w\). При \(T=p(n)\) пространственно-временная таблица имеет порядка \(T^2\) позиций; алфавит, множество состояний и локальное правило фиксированы, поэтому число переменных и локальных ограничений растёт лишь полиномиально. Размер формулы и время её построения полиномиальны по \(|w|\), поэтому получается сведение \(L\prec SAT\). Именно этот подсчёт исключает скрытый экспоненциальный рост редукции.1

Принадлежность SAT классу NP

Удовлетворяющий набор значений переменных служит кратким свидетельством выполнимости. В модели НМТ значения можно недетерминированно выбрать, после чего вычислить значение КНФ за полиномиальное время. Поэтому \(SAT\in NP\).2

Пример простыми словами

Доказательство можно представить как «фотографирование» вычисления. КНФ не вычисляет ответ вместо машины, а проверяет, существует ли корректная пространственно-временная таблица, начинающаяся с входа \(w\) и заканчивающаяся принимающим состоянием.

Частые ошибки
  • Формулировать теорему только как SAT \(\in NP\). Главный результат — NP-полнота.
  • Считать построенную КНФ описанием одной заранее известной ветви. Её выполнимость кодирует существование некоторой корректной принимающей ветви НМТ.
  • Забывать полиномиальность самого преобразования \(w\mapsto A(w)\). Без неё это не полиномиальная сводимость.

Другие вопросы

Источники

  1. 1 Сапоженко А. А. Некоторые вопросы сложности алгоритмов М.: МГУ, факультет ВМК, 2001 г. §§4–5, теорема Кука и принадлежность ВЫП классу NP
  2. 2 Кафедра математической кибернетики ВМК МГУ. Полиномиальная сводимость. NP-полнота. Теорема Кука—Левина Полнотекстовая презентация курса «Основы кибернетики», 2026 г., часть 5. Формулировка и двухчастная схема доказательства