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

редактировать

Логическая выполнимость является NP-полной, и поэтому Существуют NP-полные проблемы

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

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

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

Содержание

1 Вклад
2 Определения
3 Идея
4 Доказательство
5 Последствия
6 Ссылки

Вклад

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

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

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

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

Определения

A проблема решения находится в NP, если она может быть решена с помощью недетерминированного алгоритма за полиномиальное время.

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

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

Идея

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

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

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

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

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

SAT находится в NP, потому что любое присвоение логических значений логическим переменным, которое заявлено удовлетворение данного выражения может быть проверено за полиномиальное время с помощью детерминированной машины Тьюринга. (Утверждения проверяемые за полиномиальное время с помощью детерминированной машины Тьюринга и разрешимые за полиномиальное время с помощью недетерминированной машины Тьюринга полностью эквивалент, и доказательство можно найти во многих учебниках, например, Sipser's Introduction to theory of Computing, раздел 7.3., а также в статье Wikipedia о NP ).

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

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

Логическое выражение использует указанные переменные в следующей таблице. Здесь q ∈ Q, −p (n) ≤ i ≤ p (n), j ∈ Σ и 0 ≤ k ≤ p (n).

Переменные	Предполагаемая интерпретация	Сколько?
Ti, j, k	Истинно, если ячейка i ленты содержит символ j на этапе k вычисления.	O (p (n))
Hi, k	Истинно, если головка чтения / записи M находится в ячейке ленты i на этапе k вычисления.	O (p (n))
Qq, k	Истинно, если M находится в состоянии q на этапе k вычисления.	O (p (n))

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

Выражение	Условия	Интерпретация	Сколько?
$T i, j, 0 {\ displaystyle T_ {i, j, 0}}$ ${\ displaystyle T_ {я, j, 0}}$	Ячейка ленты i изначально содержит символ j	Исходное содержимое ленты. Для i>n-1 и i <0, за пределами фактического ввода $I {\ displaystyle I}$ $I$ , начальный символ является специальным символом по умолчанию / пустым символом.	O (p (n))
$Q s, 0 {\ displaystyle Q_ {s, 0}}$ ${\ displaystyle Q_ {s, 0}}$		Начальное состояние M.	1
$H 0, 0 {\ displaystyle H_ { 0,0}}$ ${\ displaystyle H_ {0,0}}$		Исходное положение головки чтения / записи.	1
$¬ T я, J, К ∨ ¬ T я, J ', К {\ Displaystyle \ Neg T_ {i, j, k} \ lor \ neg T_ {i, j', k}}$ $\neg T_{i,j,k}\lor \neg T_{i,j',k}$	j ≠ j ′	Не более одного символа на ячейку ленты.	О (п (п))
$⋁ j ∈ Σ T i, j, k {\ displaystyle \ bigvee _ {j \ in \ Sigma} T_ {i, j, k}}$ ${\ displaystyle \ bigvee _ {j \ in \ Sigma} T_ {i, j, k}}$		По крайней мере, один символ на ячейку ленты.	О (п (п))
$Т я, J, К ∧ Т я, J ', К + 1 → H я, к {\ Displaystyle T_ {я, j, k} \ земля T_ {i, j ', k + 1} \ rightarrow H_ {i, k}}$ $T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}$	j ≠ j ′	Лента остается неизменной, если не записана.	O (p (n))
¬Qq, k ∨ ¬Q q ′, k	q ≠ q ′	Только одно состояние в время.	O (p (n))
¬Hi, k ∨ ¬H i ′, k	i ≠ i ′	Только одно положение головы в время.	O (p (n))
$(H i, k ∧ Q q, k ∧ T i, σ, k) → ⋁ ((q, σ), (q ′, σ ′, г)) ∈ δ (ЧАС я + d, К + 1 ∧ Q q ', к + 1 ∧ Т я, σ', к + 1) {\ Displaystyle {\ begin {array} {l} (H_ {я, k} \ land Q_ {q, k} \ land T_ {i, \ sigma, k}) \ to \\\ bigvee _ {((q, \ sigma), (q ', \ sigma', d)) \ в \ delta} (H_ {i + d, \ k + 1} \ land Q_ {q ', \ k + 1} \ land T_ {i, \ \ sigma', \ k + 1}) \ end {array} }}$ ${\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	Возможные переходы на шаге вычислений k, когда голова находится в позиции i.	О (п (п))
$⋁ 0 ≤ К ≤ п (п) ⋁ е ∈ FQ е, к {\ Displaystyle \ bigvee _ {0 \ Leq к \ Leq р (п)} \ bigvee _ {f \ in F} Q_ {f, k}}$ ${\ displaystyle \ bigvee _ {0 \ leq k \ leq p (n)} \ bigvee _ {f \ in F} Q_ {е, 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)). Таким образом, преобразование, безусловно, является редукцией "многие-единицы" за полиномиальное время, как и требуется.

Последствия

Доказательство показывает, что любая проблема в 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 - новая переменная, которая больше не будет использоваться в выражении. Пункты с менее чем 3 атомами может быть дополнено; например, A можно заменить на (A ∨ A ∨ A), а (A ∨ B) можно заменить на (A ∨ B ∨ B)).

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

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

Ссылки