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

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

Теорема названа в честь Стивена Кука и Леонида Левина . Доказательство принадлежит Ричарду Карпу и основано на более раннем доказательстве (с использованием другого понятия сводимости) Кука . ^[1]

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

Взносы

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

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

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

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

Определения

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

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

Идея

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

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

Это доказательство основано на доказательстве, приведенном Гари и Джонсоном, 1979 , стр. 38–44, раздел 2.6.

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

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

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

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

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

Переменные	Предполагаемая интерпретация	Сколько? ^[6]
$T_{i,j,k}$	Истинно, если ленточная ячейка $i$ содержит символ $j$ на шаге $k$ вычисления.	$O(p(n)^{2})$
$H_{i,k}$	Правда, если $M$ головка чтения/записи находится в ячейке ленты $i$ на шаге $k$ вычисления.	$O(p(n)^{2})$
$Q_{q,k}$	Правда, если $M$ находится в состоянии $q$ на шаге $k$ вычисления.	$O(p(n))$

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

Выражение	Условия	Интерпретация	Сколько?
$T_{i,j,0}$	Ленточная ячейка $i$ изначально содержит символ $j$	Начальное содержание ленты. Для $i>n-1$ и $i<0$ , за пределами фактического ввода $I$ , начальный символ — это специальный символ по умолчанию/пустой символ.	$O(p(n))$
$Q_{s,0}$		Исходное состояние $M$ .	1
$H_{0,0}$		Исходное положение головки чтения/записи.	1
$\neg T_{i,j,k}\lor \neg T_{i,j',k}$	$j\neq j'$	Не более одного символа на ячейку ленты.	$O(p(n)^{2})$
$\bigvee _{j\in \Sigma }T_{i,j,k}$		По крайней мере, один символ на ячейку ленты.	$O(p(n)^{2})$
$T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}$	$j\neq j'$	Лента остается неизменной, если не записана руководителем.	$O(p(n)^{2})$
$\lnot Q_{q,k}\lor \lnot Q_{q',k}$	$q\neq q'$	Не более одного состояния за раз.	$O(p(n))$
$\bigvee _{q\in Q}Q_{q,k}$		Хотя бы одно государство за раз.	$O(p(n))$
$\lnot H_{i,k}\lor \lnot H_{i',k}$	$i\neq i'$	Максимум одно положение головы за раз.	$O(p(n)^{3})$
$\bigvee _{-p(n)\leq i\leq p(n)}H_{i,k}$		Хотя бы одно положение головы за раз.	$O(p(n)^{2})$
${\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<p(n)$	Возможные переходы на этапе расчета $k$ когда голова находится в положении $i$ .	$O(p(n)^{2})$
$\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)^{2})$ Логические переменные, каждая из которых может быть закодирована в пространстве $O(\log p(n))$ . Количество пунктов $O(p(n)^{3})$ ^[7] так что размер $B$ является $O(\log(p(n))p(n)^{3})$ . Таким образом, преобразование, безусловно, представляет собой сокращение «много-один» за полиномиальное время, как и требуется.

Только первая строка таблицы ( $T_{i,j,0}$ ) на самом деле зависит от входной строки $I$ . Остальные строки зависят только от входной длины $n$ и на машине $M$ ; они формализуют общее вычисление $M$ до $p(n)$ шаги.

Преобразование широко использует полином $p(n)$ . Как следствие, приведенное выше доказательство не является конструктивным : даже если $M$ известно, что, свидетельствуя о принадлежности данной задачи к NP, преобразование не может быть эффективно вычислено, если не установлена верхняя оценка $p(n)$ из $M$ временная сложность также известна.

Сложность

Хотя приведенный выше метод кодирует недетерминированную машину Тьюринга по сложности $O(\log(p(n))p(n)^{3})$ , в литературе описаны более сложные подходы по сложности $O(p(n)\log(p(n)))$ . ^[8]^[9]^[10]^[11]^[12] Квазилинейный результат впервые появился через семь лет после первоначальной публикации Кука.

Использование SAT для доказательства существования NP-полной задачи можно распространить на другие вычислительные задачи в логике, а также на полноту для других классов сложности . Проблема количественной булевой формулы (QBF) включает в себя булевы формулы, расширенные за счет включения вложенных кванторов универсальности и кванторов существования для ее переменных. Проблема QBF может использоваться для кодирования вычислений с помощью машины Тьюринга, ограниченной сложностью полиномиального пространства , доказывая, что существует проблема (распознавание истинных количественных булевых формул), которая является PSPACE-полной . Аналогично, логические формулы с количественной оценкой зависимостей кодируют вычисления с помощью машины Тьюринга, ограниченной сложностью логарифмического пространства , доказывая, что существует проблема, которая является NL-полной . ^[13]^[14]

Последствия

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

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

Карп показал, что каждая из его задач является NP-полной, сводя к этой задаче другую задачу (как уже было показано, что NP-полна). Например, он показал, что проблема 3SAT ( булева проблема выполнимости для выражений в конъюнктивной нормальной форме (CNF) ровно с тремя переменными или отрицаниями переменных в каждом предложении) является NP-полной, показав, как сократить (за полиномиальное время) любой экземпляр SAT на эквивалентный экземпляр 3SAT. ^[15]

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

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

Ссылки

^ Jump up to: ^а ^б ^с Карп, Ричард М. (1972). «Сводимость среди комбинаторных задач». У Раймонда Э. Миллера; Джеймс В. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. стр. 85–103. ISBN 0-306-30707-3 .
^ Кук, Стивен (1971). «Сложность процедур доказательства теорем» . Труды третьего ежегодного симпозиума ACM по теории вычислений . стр. 151–158. дои : 10.1145/800157.805047 . ISBN 9781450374644 . S2CID 7573663 .
^ Т.П. Бейкер; Дж. Гилл; Р. Соловей (1975). «Релятивизация вопроса P = NP». SIAM Journal по вычислительной технике . 4 (4): 431–442. дои : 10.1137/0204037 .
^ Дехтияр, М. (1969). «О невозможности устранения перебора при вычислении функции относительно ее графика». Известия Академии наук СССР (на русском языке). 14 : 1146–1148.
^ Levin, Leonid (1973). "Универсальные задачи перебора" [Universal search problems]. Problems of Information Transmission (in Russian). 9 (3): 115–116. Translated into English by Трахтенброт, бакалавр (1984). «Обзор российских подходов к алгоритмам перебора ». Анналы истории вычислительной техники . 6 (4): 384–400. дои : 10.1109/MAHC.1984.10036 . S2CID 950581 . Перевод см. в приложении, стр.399-400.
^ В этом столбце используется O. большая буква
^ Количество литералов в каждом предложении не зависит от $n$ , за исключением последней строки таблицы, которая приводит к предложению с $O(p(n))$ литералы.
^ Клаус-Петер Шнорр (январь 1978 г.). «Выполнимость квазилинейно полная в NQL» (PDF) . Журнал АКМ . 25 (1): 136–145. дои : 10.1145/322047.322060 . S2CID 1929802 .
^ Николас Пиппенджер и Майкл Дж. Фишер (апрель 1979 г.). «Отношения между мерами сложности» (PDF) . Журнал АКМ . 26 (2): 361–381. дои : 10.1145/322123.322138 . S2CID 2432526 .
^ Джон Майкл Робсон (февраль 1979 г.). Новое доказательство NP-полноты выполнимости . Материалы 2-й Австралийской конференции по информатике . стр. 62–70.
^ Джон Майкл Робсон (май 1991 г.). "Ан $O(T\log T)$ сокращение от вычислений в оперативной памяти до выполнимости» . Theoretical Computer Science . 82 (1): 141–149. doi : 10.1016/0304-3975(91)90177-4 .
^ Стивен А. Кук (январь 1988 г.). «Краткие пропозициональные формулы представляют собой недетерминированные вычисления» (PDF) . Письма об обработке информации . 26 (5): 269–270. дои : 10.1016/0020-0190(88)90152-4 .
^ Гэри Л. Петерсон; Джон Х. Рейф (1979). «чередование нескольких человек» . В книге Рональда В.; Пол Янг (ред.). Учеб. 20-й ежегодный симпозиум по основам информатики (SFCS) . IEEE. стр. 348–363.
^ Гэри Петерсон; Джон Рейф; Салман Азхар (апрель 2001 г.). «Нижние границы для многопользовательских некооперативных игр с неполной информацией» . Компьютеры и математика с приложениями . 41 (7–8): 957–992. дои : 10.1016/S0898-1221(00)00333-3 .
^ Сначала измените доказательство теоремы Кука-Левина так, чтобы полученная формула имела конъюнктивную нормальную форму, затем введите новые переменные для разделения предложений с более чем 3 атомами. Например, оговорка $(A\lor B\lor C\lor D)$ можно заменить союзом предложений $(A\lor B\lor Z)\land (\lnot Z\lor C\lor D)$ , где $Z$ — это новая переменная, которая больше нигде в выражении не будет использоваться. Предложения, содержащие менее трех атомов, могут быть дополнены; например, $(A\lor B)$ можно заменить на $(A\lor B\lor B)$ .
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 .

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

[2] Кук, Стивен (1971). «Сложность процедур доказательства теорем» . Труды третьего ежегодного симпозиума ACM по теории вычислений . стр. 151–158. дои : 10.1145/800157.805047 . ISBN 9781450374644 . S2CID 7573663 .

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

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

[5] Levin, Leonid (1973). "Универсальные задачи перебора" [Universal search problems]. Problems of Information Transmission (in Russian). 9 (3): 115–116. Translated into English by Трахтенброт, бакалавр (1984). «Обзор российских подходов к алгоритмам перебора ». Анналы истории вычислительной техники . 6 (4): 384–400. дои : 10.1109/MAHC.1984.10036 . S2CID 950581 . Перевод см. в приложении, стр.399-400.

[6] В этом столбце используется O. большая буква

[7] Количество литералов в каждом предложении не зависит от $n$ , за исключением последней строки таблицы, которая приводит к предложению с $O(p(n))$ литералы.

[8] Клаус-Петер Шнорр (январь 1978 г.). «Выполнимость квазилинейно полная в NQL» (PDF) . Журнал АКМ . 25 (1): 136–145. дои : 10.1145/322047.322060 . S2CID 1929802 .

[9] Николас Пиппенджер и Майкл Дж. Фишер (апрель 1979 г.). «Отношения между мерами сложности» (PDF) . Журнал АКМ . 26 (2): 361–381. дои : 10.1145/322123.322138 . S2CID 2432526 .

[10] Джон Майкл Робсон (февраль 1979 г.). Новое доказательство NP-полноты выполнимости . Материалы 2-й Австралийской конференции по информатике . стр. 62–70.

[11] Джон Майкл Робсон (май 1991 г.). "Ан $O(T\log T)$ сокращение от вычислений в оперативной памяти до выполнимости» . Theoretical Computer Science . 82 (1): 141–149. doi : 10.1016/0304-3975(91)90177-4 .

[12] Стивен А. Кук (январь 1988 г.). «Краткие пропозициональные формулы представляют собой недетерминированные вычисления» (PDF) . Письма об обработке информации . 26 (5): 269–270. дои : 10.1016/0020-0190(88)90152-4 .

[13] Гэри Л. Петерсон; Джон Х. Рейф (1979). «чередование нескольких человек» . В книге Рональда В.; Пол Янг (ред.). Учеб. 20-й ежегодный симпозиум по основам информатики (SFCS) . IEEE. стр. 348–363.

[14] Гэри Петерсон; Джон Рейф; Салман Азхар (апрель 2001 г.). «Нижние границы для многопользовательских некооперативных игр с неполной информацией» . Компьютеры и математика с приложениями . 41 (7–8): 957–992. дои : 10.1016/S0898-1221(00)00333-3 .

[15] Сначала измените доказательство теоремы Кука-Левина так, чтобы полученная формула имела конъюнктивную нормальную форму, затем введите новые переменные для разделения предложений с более чем 3 атомами. Например, оговорка $(A\lor B\lor C\lor D)$ можно заменить союзом предложений $(A\lor B\lor Z)\land (\lnot Z\lor C\lor D)$ , где $Z$ — это новая переменная, которая больше нигде в выражении не будет использоваться. Предложения, содержащие менее трех атомов, могут быть дополнены; например, $(A\lor B)$ можно заменить на $(A\lor B\lor B)$ .

[16] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]