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

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

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

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

Взносы

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

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

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

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

Определения

А проблема решения является в НП если это может быть решено недетерминированный алгоритм в полиномиальное время.

An пример проблемы булевой выполнимости это Логическое выражение это объединяет Булевы переменные с помощью Логические операторы.

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

Идея

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

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

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

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

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

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

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

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

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

Переменные	Предполагаемая интерпретация	Как много?
Т_{я, j, k}	Верно, если ленточная ячейка я содержит символ j на шаге k вычисления.	O (п(п)²)
ЧАС_{я, к}	Верно, если Mголовка чтения / записи находится в ячейке ленты я на шаге k вычисления.	O (п(п)²)
Q_{q, k}	Верно, если M в состоянии q на шаге k вычисления.	O (п(п))

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

Выражение	Условия	Интерпретация	Как много?
${ displaystyle T_ {i, j, 0}}$	Ленточная ячейка я изначально содержит символ j	Исходное содержание ленты. Для я > п-1 и я <0, вне фактического ввода ${ displaystyle I}$ , начальный символ - это специальный пустой символ по умолчанию.	O (п(п))
${ displaystyle Q_ {s, 0}}$		Исходное состояние M.	1
${ displaystyle H_ {0,0}}$		Исходное положение головки чтения / записи.	1
${ Displaystyle neg T_ {я, j, k} lor neg T_ {i, j ', k}}$	j ≠ j ′	Не более одного символа на ячейку ленты.	O (п(п)²)
${ displaystyle bigvee _ {j in Sigma} T_ {i, j, k}}$		По крайней мере, один символ на ячейку ленты.	O (п(п)²)
${ displaystyle T_ {i, j, k} land T_ {i, j ', k + 1} rightarrow H_ {i, k}}$	j ≠ j ′	Лента остается неизменной, если не написано.	O (п(п)²)
¬Q_{q, k} ∨ ¬Q_{q ′, k}	q ≠ q ′	Только одно состояние за раз.	O (п(п))
¬ЧАС_{я, к} ∨ ¬ЧАС_{я, к}	я ≠ я'	Только одно положение головы за раз.	O (п(п)³)
${ 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<п(п)	Возможные переходы на этапе расчета k когда голова в положении я.	O (п(п)²)
${ displaystyle bigvee _ {0 leq k leq p (n)} bigvee _ {f in F} Q_ {f, k}}$		Должен закончиться в состоянии принятия, не позднее, чем на шаге п(п).	1

Если есть приемлемое вычисление для M на входе я, тогда B выполняется путем присвоения Т_{я, j, k}, ЧАС_{я, к} и Q_{я, к} их предполагаемые интерпретации. С другой стороны, если B выполнимо, то есть приемлемое вычисление для M на входе я который следует за шагами, указанными присвоениями переменных.

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

Последствия

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

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

Карп показал, что каждая из его проблем является 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-полноты,^[6] и все еще обнаруживаются новые проблемы, относящиеся к этому классу сложности.

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

использованная литература

^ Повар, Стивен (1971). «Сложность процедур доказательства теорем». Материалы третьего ежегодного симпозиума ACM по теории вычислений. С. 151–158. Дои:10.1145/800157.805047.
^ ^а ^б Карп, Ричард М. (1972). «Сводимость среди комбинаторных проблем» (PDF). В Раймонде Э. Миллере; Джеймс У. Тэтчер (ред.). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103. ISBN 0-306-30707-3.
^ Т. П. Бейкер; Дж. Гилл; Р. Соловей (1975). «Релятивизации вопроса P = NP». SIAM Журнал по вычислениям. 4 (4): 431–442. Дои:10.1137/0204037.
^ Дехтияр, М. (1969). «О невозможности устранения перебора при вычислении функции относительно ее графика». Известия АН СССР. (по-русски). 14: 1146–1148.
^ Левин Леонид (1973). "Универсальные задачи перебора" [Универсальные поисковые задачи]. Проблемы передачи информации (по-русски). 9 (3): 115–116. Переведено на английский язык Трахтенброт, Б.А. (1984). "Обзор российских подходов к перебор (перебором) алгоритмов ". Анналы истории вычислительной техники. 6 (4): 384–400. Дои:10.1109 / MAHC.1984.10036.
^ ^а ^б Garey, Michael R .; Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман. ISBN 0-7167-1045-5.

[1] Повар, Стивен (1971). «Сложность процедур доказательства теорем». Материалы третьего ежегодного симпозиума ACM по теории вычислений. С. 151–158. Дои:10.1145/800157.805047.

[Karp-2] а ^б Карп, Ричард М. (1972). «Сводимость среди комбинаторных проблем» (PDF). В Раймонде Э. Миллере; Джеймс У. Тэтчер (ред.). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103. ISBN 0-306-30707-3.

[3] Т. П. Бейкер; Дж. Гилл; Р. Соловей (1975). «Релятивизации вопроса P = NP». SIAM Журнал по вычислениям. 4 (4): 431–442. Дои:10.1137/0204037.

[4] Дехтияр, М. (1969). «О невозможности устранения перебора при вычислении функции относительно ее графика». Известия АН СССР. (по-русски). 14: 1146–1148.

[5] Левин Леонид (1973). "Универсальные задачи перебора" [Универсальные поисковые задачи]. Проблемы передачи информации (по-русски). 9 (3): 115–116. Переведено на английский язык Трахтенброт, Б.А. (1984). "Обзор российских подходов к перебор (перебором) алгоритмов ". Анналы истории вычислительной техники. 6 (4): 384–400. Дои:10.1109 / MAHC.1984.10036.

[Garey-6] а ^б Garey, Michael R .; Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман. ISBN 0-7167-1045-5.

[1]

[2]

[3]

[4]

[5]

[6]