В теории сложности вычислений , то теорема Кук-Левин , также известная как теорема Кука , гласит , что булева задача выполнимости является NP-полной . То есть она находится в NP , и любая проблема в NP может быть сведена за полиномиальное время с помощью детерминированной машины Тьюринга к проблеме булевой выполнимости.
Теорема названа в честь Стивена Кука и Леонида Левина .
Важным следствием этой теоремы является то, что если существует детерминированный алгоритм с полиномиальным временем для решения булевой выполнимости, то каждая проблема NP может быть решена с помощью детерминированного алгоритма с полиномиальным временем. Таким образом, вопрос о том, существует ли такой алгоритм для булевой выполнимости, эквивалентен проблеме P и NP , которая широко считается наиболее важной нерешенной проблемой в теоретической информатике.
Взносы
Концепция NP-полноты была разработана в конце 1960-х - начале 1970-х годов параллельно исследователями из Северной Америки и СССР . В 1971 году Стивен Кук опубликовал свою статью «Сложность процедур доказательства теорем» [1] в материалах конференции недавно основанного ACM Symposium on Theory of Computing . Последующая статья Ричарда Карпа «Сводимость среди комбинаторных проблем» [2] вызвала новый интерес к статье Кука, предоставив список из 21 NP-полной проблемы . Кук и Карп получили за эту работу премию Тьюринга .
Теоретический интерес к NP-полноте был также усилен работой Теодора П. Бейкера, Джона Гилла и Роберта Соловея, которые показали, что решение NP-задач в моделях машин Oracle требует экспоненциального времени. То есть, существует оракул A таких , что для всех субэкспоненциальных детерминированных классов сложности времени Т, то релятивизованная сложность класс NP не является подмножество Т А . В частности, для этого оракула, P A ≠ NP A . [3]
В СССР результат, эквивалентный результатам Бейкера, Гилла и Соловая, был опубликован в 1969 г. М. Дехтияром. [4] Позднее в 1973 году была опубликована статья Леонида Левина «Универсальные поисковые задачи» [5] , хотя она упоминалась в обсуждениях и была представлена к публикации несколькими годами ранее.
Подход Левина немного отличался от подхода Кука и Карпа в том, что он рассматривал проблемы поиска , которые требуют поиска решений, а не простого определения существования. Он предоставил 6 таких NP-полных задач поиска или универсальных задач . Кроме того, он нашел для каждой из этих проблем алгоритм, который решает ее за оптимальное время (в частности, эти алгоритмы работают за полиномиальное время тогда и только тогда, когда P = NP ).
Определения
Проблема решения находится в НП , если она может быть решена с помощью недетерминистическую алгоритма в полиномиальное время .
Примером проблемы логической выполнимости является логическое выражение, которое объединяет логические переменные с помощью логических операторов .
Выражение является выполнимым, если переменным присваиваются значения истинности, которые делают все выражение истинным.
Идея
Для любой проблемы решения в NP постройте недетерминированную машину, которая решает ее за полиномиальное время. Затем для каждого ввода в эту машину создайте логическое выражение, которое вычисляет, передается ли этот конкретный ввод машине, машина работает правильно, а машина останавливается и отвечает «да». Тогда выражение может быть удовлетворено тогда и только тогда, когда есть способ для машины работать правильно и отвечать «да», поэтому выполнимость сконструированного выражения эквивалентна вопросу, ответит ли машина «да».
Доказательство
Это доказательство основано на доказательстве, приведенном Гэри и Джонсоном. [6]
Доказательство того, что проблема логической выполнимости (SAT) является NP-полной, состоит из двух частей. Один из них - показать, что SAT - это проблема NP. Другой - показать, что каждая проблема NP может быть сведена к экземпляру проблемы SAT с помощью полиномиального сокращения многих единиц .
SAT находится в NP, потому что любое присвоение логических значений логическим переменным, которое, как утверждается, удовлетворяет данному выражению, может быть проверено за полиномиальное время с помощью детерминированной машины Тьюринга. (Утверждения, проверяемые за полиномиальное время с помощью детерминированной машины Тьюринга и разрешимые за полиномиальное время с помощью недетерминированной машины Тьюринга , полностью эквивалентны, и доказательство можно найти во многих учебниках, например, во введении Сипсера в теорию вычислений , раздел 7.3. ., а также в статье в Википедии о НП ).
Теперь предположим, что заданная задача в NP может быть решена с помощью недетерминированной машины Тьюринга M = ( Q , Σ, s , F , δ) , где Q - множество состояний, Σ - алфавит символов ленты, s ∈ Q - начальное состояние, F ⊆ Q - множество принимающих состояний, а δ ⊆ (( Q \ F ) × Σ) × ( Q × Σ × {−1, +1}) - отношение перехода. Предположим далее, что M принимает или отклоняет экземпляр проблемы за время p ( n ), где n - размер экземпляра, а p - полиномиальная функция.
Для каждого входа, я , мы указываем логическое выражение , которое выполнима тогда и только тогда , когда машина M принимает I .
В логическом выражении используются переменные, указанные в следующей таблице. Здесь q ∈ Q , - p ( n ) ≤ i ≤ p ( n ), j ∈ Σ и 0 ≤ k ≤ p ( n ) .
Переменные | Предполагаемая интерпретация | Сколько? |
---|---|---|
Т я, j, k | Истинно, если ячейка ленты i содержит символ j на шаге k вычисления. | О ( п ( п ) 2 ) |
H i, k | Истинно, если головка чтения / записи M находится в ячейке ленты i на этапе k вычисления. | О ( п ( п ) 2 ) |
Q q, k | Истинно, если M находится в состоянии q на шаге k вычисления. | О ( п ( п )) |
Определите логическое выражение B как соединение подвыражений из следующей таблицы для всех - p ( n ) ≤ i ≤ p ( n ) и 0 ≤ k ≤ p ( n ) :
Выражение | Условия | Интерпретация | Сколько? |
---|---|---|---|
Ленточная ячейка i изначально содержит символ j | Исходное содержание ленты. Для i > n -1 и i <0, вне фактического ввода, начальный символ является специальным пустым символом по умолчанию. | О ( п ( п )) | |
Исходное состояние М . | 1 | ||
Исходное положение головки чтения / записи. | 1 | ||
j ≠ j ′ | Не более одного символа на ячейку ленты. | О ( п ( п ) 2 ) | |
По крайней мере, один символ на ячейку ленты. | О ( п ( п ) 2 ) | ||
j ≠ j ′ | Лента остается неизменной, если не написано. | О ( п ( п ) 2 ) | |
¬ Q q, k ∨ ¬ Q q ′, k | q ≠ q ′ | Только одно состояние за раз. | О ( п ( п )) |
¬ H i, k ∨ ¬ H i ′, k | я ≠ я | Только одно положение головы за раз. | О ( п ( п ) 3 ) |
к < р ( п ) | Возможные переходы на шаге вычисления k, когда голова находится в положении i . | О ( п ( п ) 2 ) | |
Должен завершиться в состоянии принятия не позднее, чем на шаге 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 ), поэтому размер B равен O (log ( p ( n )) p ( n ) 3 ). Таким образом, преобразование, безусловно, является редукцией "многие-единицы" за полиномиальное время, как и требуется.
Последствия
Доказательство показывает, что любую задачу в 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 - новая переменная, которая больше не будет использоваться в выражении. можно дополнить; например, A можно заменить на (A ∨ A ∨ A), а (A ∨ B) можно заменить на (A ∨ B ∨ B)).
Garey и Джонсон представили более 300 NP-полных задач в своей книге Компьютеры и труднорешаемые: Руководство по теории NP-полноты , [6] и новые проблемы все еще обнаруживаются в пределах этой сложности класса.
Хотя многие практические примеры SAT могут быть решены эвристическими методами , вопрос о том, существует ли детерминированный алгоритм с полиномиальным временем для SAT (и, следовательно, всех других NP-полных проблем), все еще остается известной нерешенной проблемой, несмотря на десятилетия интенсивных усилий теоретики сложности, математические логики и другие. Подробнее читайте в статье Проблема P и NP .
Рекомендации
- ^ Кук, Стивен (1971). «Сложность процедур доказательства теорем» . Материалы третьего ежегодного симпозиума ACM по теории вычислений . С. 151–158. DOI : 10,1145 / 800157.805047 .
- ^ а б Карп, Ричард М. (1972). «Сводимость среди комбинаторных проблем» (PDF) . В Раймонде Э. Миллере; Джеймс У. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. С. 85–103. ISBN 0-306-30707-3.
- ^ Т.П. Бейкер; Дж. Гилл; Р. Соловей (1975). «Релятивизации вопроса P = NP». SIAM Journal on Computing . 4 (4): 431–442. DOI : 10.1137 / 0204037 .
- ^ Дехтияр, М. (1969). «О невозможности устранения перебора при вычислении функции относительно ее графика». Известия Академии наук СССР . 14 : 1146–1148.
- ^ Левин, Леонид (1973). "Универсальные задачи перебора" [Универсальные поисковые задачи]. Проблемы передачи информации . 9 (3): 115–116. Переведено на английский язык Трахтенброт, Б.А. (1984). «Обзор российских подходов к алгоритмам перебора». Анналы истории вычислительной техники . 6 (4): 384–400. DOI : 10.1109 / MAHC.1984.10036 .
- ^ а б Garey, Michael R .; Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5.