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

Теорема Кука — Левина — фундаментальный результат теории сложности вычислений, устанавливающий существование NP-полных задач. Теорема, независимо доказанная Стивеном Куком в 1971 году и Леонидом Левиным в 1973 году, утверждает, что задача выполнимости булевых формул (SAT) является NP-полной. Это означает, что любая задача из класса NP может быть сведена к SAT за полиномиальное время, и если для SAT существует эффективный (полиномиальный) алгоритм решения, то все задачи класса NP также могут быть решены за полиномиальное время.

История

В конце 1960-х — начале 1970-х годов в теории сложности вычислений активно исследовались вопросы о том, какие задачи могут быть решены эффективно. Класс P (полиномиальное время) считался формальным аналогом «практически решаемых» задач, а класс NP (недетерминированное полиномиальное время) включал задачи, решение которых можно быстро проверить, но не обязательно быстро найти.

В 1971 году американский математик Стивен Кук в статье «The Complexity of Theorem-Proving Procedures» впервые сформулировал и доказал, что задача SAT является NP-полной. Он показал, что для любой задачи из NP можно построить булеву формулу, которая выполнима тогда и только тогда, когда исходная задача имеет решение. Это построение осуществляется за полиномиальное время.

Независимо от Кука, в 1973 году советский математик Леонид Левин в статье «Универсальные задачи перебора» (опубликованной в журнале «Проблемы передачи информации») пришёл к аналогичному результату. Левин рассматривал не только SAT, но и другие задачи, такие как задача о покрытии множества и задача о коммивояжёре, и доказал их «универсальность» в том же смысле. В западной литературе результат часто называют теоремой Кука, а в российской — теоремой Кука — Левина.

Формулировка

Теорема Кука — Левина утверждает:

Задача выполнимости булевых формул (SAT) является NP-полной.

Это означает два свойства:

SAT принадлежит классу NP (решение задачи можно проверить за полиномиальное время, подставив значения переменных в формулу).
Любая задача из класса NP сводится к SAT за полиномиальное время (SAT является NP-трудной).

Доказательство (краткая схема)

Доказательство состоит из двух частей: проверка принадлежности SAT к NP и доказательство NP-трудности.

Принадлежность SAT к NP

Для данной булевой формулы в конъюнктивной нормальной форме (КНФ) и набора значений переменных можно за полиномиальное время вычислить значение формулы. Если формула истинна, то данный набор является сертификатом. Таким образом, SAT ∈ NP.

NP-трудность SAT

Необходимо показать, что для любой задачи L ∈ NP существует полиномиальное сведение к SAT. По определению NP, существует недетерминированная машина Тьюринга M, которая решает L за полиномиальное время p(n). Идея сведения: для каждого входа x длины n строится булева формула φ, которая описывает все возможные вычисления M на входе x. Формула φ выполнима тогда и только тогда, когда существует последовательность конфигураций M, ведущая к принимающему состоянию.

Построение включает:

Переменные: описывают состояние ленты, положение головки и состояние машины на каждом шаге вычисления (всего O(p(n)²) переменных).
Клозы: описывают начальную конфигурацию, условия корректности перехода между конфигурациями (согласно программе M), и условие достижения принимающего состояния.

Размер формулы φ полиномиален относительно n, и её построение выполняется за полиномиальное время. Если M принимает x, то существует последовательность конфигураций, удовлетворяющая φ. Обратно, если φ выполнима, то существует принимающее вычисление M на x. Таким образом, L сводится к SAT.

Значение и следствия

Основа теории NP-полноты

Теорема Кука — Левина является отправной точкой для доказательства NP-полноты многих других задач. После установления NP-полноты SAT, для доказательства NP-полноты новой задачи достаточно показать, что:

задача принадлежит NP;
к ней можно свести SAT (или другую известную NP-полную задачу) за полиномиальное время.

Таким образом, была построена целая иерархия NP-полных задач, включающая такие классические проблемы, как:

задача о выполнимости 3-КНФ (3-SAT);
задача о клике;
задача о вершинном покрытии;
задача о гамильтоновом цикле;
задача коммивояжёра;
задача о рюкзаке;
задача о раскраске графа.

Проблема P vs NP

Теорема Кука — Левина непосредственно связана с центральной нерешённой проблемой современной информатики — вопросом о равенстве классов P и NP. Если P = NP, то для SAT существует полиномиальный алгоритм, и, следовательно, для всех NP-полных задач существуют полиномиальные алгоритмы. Если P ≠ NP, то для NP-полных задач не существует эффективных алгоритмов, и они остаются «трудными» для точного решения.

Большинство исследователей склоняются к гипотезе, что P ≠ NP, однако строгого доказательства этого факта до сих пор не получено.

Практические применения

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

Вариации и обобщения

SAT и его варианты

3-SAT: задача выполнимости для формул в 3-КНФ (каждая скобка содержит ровно три литерала). 3-SAT также является NP-полной и часто используется в доказательствах сведения.
MAX-SAT: задача поиска максимального числа выполнимых скобок. Является NP-трудной, но не NP-полной, так как не является задачей распознавания.
#SAT: задача подсчёта числа выполняющих наборов. Относится к классу #P-полных задач.

Другие NP-полные задачи

После теоремы Кука — Левина было доказано, что NP-полными являются сотни задач из различных областей: логики, теории графов, комбинаторики, оптимизации, криптографии, биоинформатики и других.

Критика и ограничения

Теорема Кука — Левина является теоретическим результатом, и её практическое значение иногда оспаривается. Во-первых, сведение произвольной задачи из NP к SAT может приводить к формулам экспоненциального размера относительно n, хотя формально остаётся полиномиальным. Во-вторых, NP-полнота гарантирует трудность в худшем случае, но многие реальные задачи имеют структуру, позволяющую решать их быстро. В-третьих, существуют классы сложности, выходящие за рамки NP (например, PSPACE, EXPTIME), для которых также существуют полные задачи.

Интересные факты

Стивен Кук получил за свою работу премию Тьюринга в 1982 году.
Леонид Левин эмигрировал из СССР в США в 1978 году и впоследствии стал профессором Бостонского университета.
Теорема Кука — Левина иногда называется «теоремой Кука» в англоязычной литературе, но в русскоязычных источниках обычно используется двойное название.
Задача SAT является одной из первых задач, для которых была доказана NP-полнота, и до сих пор остаётся центральной в теории сложности.

Источники

Cook, S. A. (1971). «The Complexity of Theorem-Proving Procedures». Proceedings of the 3rd Annual ACM Symposium on Theory of Computing.
Levin, L. A. (1973). «Universal Search Problems». Problems of Information Transmission, 9(3): 265–266.
Garey, M. R., Johnson, D. S. (1979). «Computers and Intractability: A Guide to the Theory of NP-Completeness». W. H. Freeman.
Arora, S., Barak, B. (2009). «Computational Complexity: A Modern Approach». Cambridge University Press.
Sipser, M. (2012). «Introduction to the Theory of Computation» (3rd ed.). Cengage Learning.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →