Класс NP

Класс NP — это фундаментальный класс сложности в теории алгоритмов, объединяющий все задачи, для которых правильность предложенного решения может быть проверена за полиномиальное время на недетерминированной машине Тьюринга. Класс NP является одним из центральных понятий в теории сложности вычислений, а вопрос о его равенстве с классом P (задачи, решаемые за полиномиальное время) составляет одну из семи «Проблем тысячелетия», за решение которой Математическим институтом Клэя объявлен приз в 1 миллион долларов США.

Определение и формальное описание

Формально, класс NP (от англ. nondeterministic polynomial time) определяется как множество языков (задач распознавания), которые могут быть распознаны недетерминированной машиной Тьюринга за полиномиальное время. Это означает, что для любого входа длины n существует последовательность недетерминированных выборов (сертификат), которая приводит машину к принимающему состоянию не более чем за O(n^k) шагов для некоторой константы k.

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

Соотношение с классом P

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

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

NP-полнота

Центральным понятием, связанным с классом NP, является NP-полнота. Задача называется NP-полной, если она принадлежит классу NP и к ней можно свести любую другую задачу из NP за полиномиальное время (с помощью полиномиального сведения). Это означает, что NP-полные задачи являются «самыми сложными» в классе NP: если для какой-либо NP-полной задачи будет найден полиномиальный алгоритм решения, то это автоматически докажет, что P = NP.

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

Примеры NP-полных задач

К настоящему времени известно несколько тысяч NP-полных задач из различных областей математики, информатики, экономики и физики. Наиболее известные из них:

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

Класс co-NP

Класс co-NP является дополнением класса NP. Задача принадлежит co-NP, если её дополнение (отрицательный ответ) принадлежит NP. Иными словами, для задач из co-NP можно быстро проверить, что ответ является отрицательным, если предоставить соответствующий свидетель. Например, задача проверки, является ли число составным, принадлежит NP (свидетель — делитель), а задача проверки, является ли число простым, принадлежит co-NP (свидетель — доказательство простоты). В 2002 году было доказано, что задача проверки простоты принадлежит классу P (алгоритм AKS), что автоматически помещает её и в NP, и в co-NP. Вопрос о том, совпадают ли классы NP и co-NP, также остаётся открытым, хотя считается, что NP ≠ co-NP.

Практическое значение

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

• Приближённые алгоритмы — алгоритмы, которые находят решение, не обязательно оптимальное, но гарантированно не хуже некоторого порога.
• Эвристические алгоритмы — алгоритмы, которые находят «хорошие» решения, но не дают никаких гарантий качества (например, генетические алгоритмы, имитация отжига, муравьиные алгоритмы).
• Методы ветвей и границ — точные алгоритмы, которые в худшем случае работают экспоненциально долго, но на практике часто справляются с задачами умеренного размера.

Задачи из класса NP встречаются повсеместно: в планировании производства, маршрутизации транспорта, проектировании интегральных схем, биоинформатике, криптографии, искусственном интеллекте и многих других областях.

Открытые вопросы

Помимо проблемы P vs NP, с классом NP связано несколько других важных открытых вопросов:

• NP vs co-NP: совпадают ли эти классы?
• NP-полнота задачи об изоморфизме графов: неизвестно, является ли эта задача NP-полной или принадлежит классу P.
• NP-полнота задачи о разложении на множители: широко используемая в криптографии задача, её NP-полнота не доказана, но и полиномиального алгоритма для неё не найдено.

Источники

• Стивен Кук, «The complexity of theorem-proving procedures», 1971.
• Леонид Левин, «Универсальные задачи перебора», 1973.
• Майкл Гэри, Дэвид Джонсон, «Вычислительные машины и труднорешаемые задачи», 1979.
• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн, «Алгоритмы: построение и анализ», 3-е издание, 2009.
• Кристофер Мур, Стефан Мертенс, «Природа вычислений», 2011.