Теорема Кука – Левина - Cook–Levin theorem

В теории сложности вычислений , то теорема Кук-Левин , также известная как теорема Кука , гласит , что булева задача выполнимости является NP-полной . То есть она находится в NP , и любая проблема в NP может быть сведена за полиномиальное время с помощью детерминированной машины Тьюринга к проблеме булевой выполнимости.

Теорема названа в честь Стивена Кука и Леонида Левина .

Важным следствием этой теоремы является то, что если существует детерминированный алгоритм с полиномиальным временем для решения булевой выполнимости, то каждая проблема NP может быть решена с помощью детерминированного алгоритма с полиномиальным временем. Таким образом, вопрос о том, существует ли такой алгоритм для булевой выполнимости, эквивалентен проблеме P и NP , которая широко считается наиболее важной нерешенной проблемой в теоретической информатике.

Взносы

Концепция NP-полноты была разработана в конце 1960-х - начале 1970-х годов параллельно исследователями из Северной Америки и СССР . В 1971 году Стивен Кук опубликовал свою статью «Сложность процедур доказательства теорем» в материалах конференции недавно основанного симпозиума ACM по теории вычислений . Последующая статья Ричарда Карпа «Сводимость среди комбинаторных проблем» вызвала новый интерес к статье Кука, предоставив список из 21 NP-полной проблемы . Кук и Карп получили за эту работу премию Тьюринга .

Теоретический интерес к NP-полноте был также усилен работой Теодора П. Бейкера, Джона Гилла и Роберта Соловея, которые в 1975 году показали, что решение NP-задач в моделях машин Oracle требует экспоненциального времени. То есть, существует оракул A таких , что для всех субэкспоненциальных детерминированных классов сложности времени Т, то релятивизованная сложность класс NP не является подмножество Т ^А . В частности, для этого оракула, P ^A ≠ NP ^A .

В СССР результат, эквивалентный результатам Бейкера, Гилла и Соловея, был опубликован в 1969 г. М. Дехтияром. Позднее в 1973 г. была опубликована статья Леонида Левина «Универсальные поисковые задачи», хотя она упоминалась в обсуждениях и была представлена к публикации несколькими годами ранее.

Подход Левина немного отличался от подхода Кука и Карпа в том, что он рассматривал проблемы поиска , которые требуют поиска решений, а не простого определения существования. Он предоставил 6 таких NP-полных задач поиска или универсальных задач . Кроме того, он нашел для каждой из этих проблем алгоритм, который решает ее за оптимальное время (в частности, эти алгоритмы работают за полиномиальное время тогда и только тогда, когда P = NP ).

Определения

Проблема решения находится в НП , если она может быть решена с помощью недетерминистическую алгоритма в полиномиальное время .

Примером проблемы логической выполнимости является логическое выражение, которое объединяет логические переменные с помощью логических операторов .

Выражение является выполнимым, если переменным присваиваются значения истинности, которые делают все выражение истинным.

Идея

Для любой проблемы решения в NP постройте недетерминированную машину, которая решает ее за полиномиальное время. Затем для каждого ввода в эту машину создайте логическое выражение, которое вычисляет, передается ли этот конкретный ввод машине, машина работает правильно, а машина останавливается и отвечает «да». Тогда выражение может быть удовлетворено тогда и только тогда, когда есть способ для машины работать правильно и ответить «да», поэтому выполнимость сконструированного выражения эквивалентна вопросу, ответит ли машина «да».

Доказательство

Схематизированной прием вычисления на машине М .

Это доказательство основано на доказательстве, приведенном Гэри и Джонсоном.

Доказательство того, что проблема логической выполнимости (SAT) является NP-полной, состоит из двух частей. Один из них - показать, что SAT - это проблема NP. Другой - показать, что каждая проблема NP может быть сведена к экземпляру проблемы SAT с помощью полиномиального сокращения многих единиц .

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

Теперь предположим, что данную задачу в NP можно решить с помощью недетерминированной машины Тьюринга $M = (Q, Σ, s, F, δ)$ , где Q - множество состояний, Σ - алфавит символов ленты, $s \in Q$ - начальное состояние, $F \subseteq Q$ - множество принимающих состояний, а $δ ⊆ (( Q \ F ) × Σ) × ( Q × Σ × {−1, +1})$ - отношение перехода. Предположим далее, что M принимает или отклоняет экземпляр проблемы за время p ( n ), где n - размер экземпляра, а p - полиномиальная функция.

Для каждого входа, я , мы указываем логическое выражение , которое выполнима тогда и только тогда , когда машина M принимает I .

В логическом выражении используются переменные, указанные в следующей таблице. Здесь $q \in Q, - p (n) \leq i \leq p (n), j \in Σ$ и $0 \leq k \leq p (n)$ .

Переменные	Предполагаемая интерпретация	Как много?
Т _{я, j, k}	Истинно, если ячейка ленты i содержит символ j на шаге k вычисления.	О ( п ( п ) ² )
H _{i, k}	Правда , если M ' головка чтения / запись s находится на магнитной ленте клетку я на этапе к вычислению.	О ( п ( п ) ² )
Q _{q, k}	Истинно, если M находится в состоянии q на шаге k вычисления.	О ( п ( п ))

Определите логическое выражение B как соединение подвыражений из следующей таблицы для всех $- p (n) \leq i \leq p (n)$ и $0 \leq k \leq p (n)$ :

Выражение	Условия	Интерпретация	Как много?
${\ displaystyle T_ {я, j, 0}}$	Ячейка ленты i изначально содержит символ j	Исходное содержание ленты. Для i > n -1 и i <0, вне фактического ввода , начальный символ является специальным по умолчанию / пустым символом. ${\ displaystyle I}$	О ( п ( п ))
${\ displaystyle Q_ {s, 0}}$		Исходное состояние М .	1
${\ displaystyle H_ {0,0}}$		Исходное положение головки чтения / записи.	1
${\ displaystyle \ neg T_ {я, j, k} \ lor \ neg T_ {i, j ', k}}$	j ≠ j ′	Не более одного символа на ячейку ленты.	О ( п ( п ) ² )
${\ displaystyle \ bigvee _ {j \ in \ Sigma} T_ {i, j, k}}$		По крайней мере, один символ на ячейку ленты.	О ( п ( п ) ² )
${\ displaystyle T_ {i, j, k} \ land T_ {i, j ', k + 1} \ rightarrow H_ {i, k}}$	j ≠ j ′	Лента остается неизменной, если не написано.	О ( п ( п ) ² )
¬ Q _{q, k} ∨ ¬ Q _{q ′, k}	q ≠ q ′	Только одно состояние за раз.	О ( п ( п ))
¬ H _{i, k} ∨ ¬ H _{i ′, k}	я ≠ я	Только одно положение головы за раз.	О ( п ( п ) ³ )
${\ displaystyle {\ begin {array} {l} (H_ {i, k} \ land Q_ {q, k} \ land T_ {i, \ sigma, k}) \ to \\\ bigvee _ {((q , \ sigma), (q ', \ sigma', d)) \ in \ delta} (H_ {i + d, \ k + 1} \ land Q_ {q ', \ k + 1} \ land T_ {i , \ \ sigma ', \ k + 1}) \ end {array}}}$	к < р ( п )	Возможные переходы на шаге вычисления k, когда голова находится в положении i .	О ( п ( п ) ² )
${\ displaystyle \ bigvee _ {0 \ leq k \ leq p (n)} \ bigvee _ {f \ in F} Q_ {f, k}}$		Должен завершиться в состоянии принятия не позднее, чем на шаге p ( n ).	1

Если есть принимающее вычисление для M на входе I , то B выполняется путем присвоения T _{i, j, k} , H _{i, k} и Q _{i, k} их предполагаемых интерпретаций. С другой стороны, если B является выполнимым, то есть принимающее вычисление для M на входе I, которое следует шагам, указанным присваиваниями переменным.

Существует O ( p ( n ) ² ) логических переменных, каждая из которых кодируется в пространстве $O (log p (n))$ . Количество предложений равно O ( p ( n ) ³ ), поэтому размер B равен O (log ( p ( n )) p ( n ) ³ ). Таким образом, преобразование, безусловно, является редукцией "многие-единицы" за полиномиальное время, как и требуется.

Сложность

В то время как вышеупомянутый метод кодирует недетерминированную машину Тьюринга по сложности , в литературе описываются более сложные подходы по сложности . Квазилинейный результат впервые появился через семь лет после первоначальной публикации Кука. ${\ Displaystyle О (журнал (п (п)) п (п) ^ {3})}$ ${\ Displaystyle О (п (п) журнал (п (п)))}$

Обобщенные версии логической выполнимости имеют кодировки с более сильными границами: количественные булевы формулы (QBF) кодируют недетерминированные машины Тьюринга с полиномиальной сложностью по отношению к пространственной границе машины (в отличие от временной границы), а количественные логические формулы с зависимостью (DQBF) кодируют не -детерминированные машины Тьюринга с идеальной логарифмической сложностью по отношению к машинному пространству.

Последствия

Доказательство показывает, что любую задачу в NP можно свести за полиномиальное время (на самом деле, достаточно логарифмического пространства) к примеру проблемы булевой выполнимости. Это означает, что если бы проблема логической выполнимости могла быть решена за полиномиальное время с помощью детерминированной машины Тьюринга , то все проблемы в NP могли бы быть решены за полиномиальное время, и поэтому класс сложности NP был бы равен классу сложности P.

Значение NP-полноты стало ясно из публикации в 1972 году знаменательной статьи Ричарда Карпа «Сводимость среди комбинаторных проблем», в которой он показал, что 21 разнообразная комбинаторная проблема и проблема теории графов , каждая из которых печально известна своей неразрешимостью, являются NP -полный.

Карп показал, что каждая из его проблем является NP-полной, сводя к ней другую задачу (уже доказанную как NP-полную). Например, он показал, что проблема 3SAT (проблема логической выполнимости для выражений в конъюнктивной нормальной форме с ровно тремя переменными или отрицаниями переменных на предложение) является NP-полной, показывая, как сократить (за полиномиальное время) любой экземпляр SAT до эквивалентный экземпляр 3SAT. (Сначала вы модифицируете доказательство теоремы Кука – Левина, чтобы результирующая формула имела конъюнктивную нормальную форму, затем вы вводите новые переменные для разделения предложений с более чем 3 атомами. Например, предложение (A ∨ B ∨ C ∨ D) можно заменить комбинацией предложений (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), где Z - новая переменная, которая больше не будет использоваться в выражении. можно дополнить; например, A можно заменить на (A ∨ A ∨ A), а (A ∨ B) можно заменить на (A ∨ B ∨ B)).

Гэри и Джонсон представили более 300 NP-полных проблем в своей книге « Компьютеры и неразрешимость: руководство по теории NP-полноты» , и все еще обнаруживаются новые проблемы, относящиеся к этому классу сложности.

Хотя многие практические примеры SAT могут быть решены эвристическими методами , вопрос о том, существует ли детерминированный алгоритм с полиномиальным временем для SAT (и, следовательно, всех других NP-полных проблем), все еще остается известной нерешенной проблемой, несмотря на десятилетия интенсивных усилий теоретики сложности, математические логики и другие. Подробнее читайте в статье Проблема P и NP .

Languages

In other projects