NP-Полная задача

$\mathcal{N}P$-Полная задача ($\mathcal{N}P$-Complete problem) — такая задача $A$ из класса $\mathcal{N}P$ всех задач, недетерминированно разрешимых за полиномиальное время, что любая задача из $\mathcal{N}P$ полиномиально сводится к $A.$ Если требование принадлежности $A$ классу $\mathcal{N}P$ не рассматривается, то используется термин $\mathcal{N}P$-трудная задача.

Найдется немного научных терминов, так быстро завоевавших широкую известность, как понятие "$\mathcal{N}P$-полная задача". За короткий промежуток времени с момента введения этого понятия С. Куком в начале 70-х годов оно стало символом тех трудностей, которые встречаются на пути создания достаточно общих и эффективных методов решения задач дискретной математики. $\mathcal{N}P$-полные задачи являются "самыми трудными" в классе $\mathcal{N}P.$ Если какая-нибудь $\mathcal{N}P$-полная задача может быть решена за полиномиальное время, то и любая задача из $\mathcal{N}P$ полиномиально разрешима, а если какая-то задача из $\mathcal{N}P$ труднорешаема, то и любая $\mathcal{N}P$-полная задача является труднорешаемой. При этом, для того чтобы доказать $\mathcal{N}P$-полноту некоторой задачи из $\mathcal{N}P,$ достаточно показать, что какая-то из $\mathcal{N}P$-полных задач полиномиально сводится к ней.

Вопрос о взаимоотношении классов $\mathcal{P}$ и $\mathcal{N}P$ имеет фундаментальное значение, но все еще открыт. Известно, что $\mathcal{P}\subseteq \mathcal{N}P$ и если $L\in \mathcal{N}P,$ то существует такой полином $p(n)$ и ДМТ $M,$ что $L$ допускается на $M$ с временной сложностью $O(2^{p(n)}).$ Однако до сих пор не доказано, содержит класс $\mathcal{N}P$ труднорешаемые задачи или нет, т. е. $\mathcal{N}P\setminus P\ne \mathrm{\varnothing }$ или $\mathcal{N}P=P.$ Вместе с тем известно, что в предположении $\mathcal{P}\ne \mathcal{N}P$ класс $\mathcal{N}P$ не просто содержит два непересекающихся подкласса: класс $\mathcal{P}$ и класс $\mathcal{N}P$-полных задач, а также должен включать задачи, не принадлежащие ни одному из этих подклассов (т.е. при $\mathcal{P}\ne \mathcal{N}P$ должны существовать задачи из $\mathcal{N}P,$ которые неразрешимы за полиномиальное время и не являются $\mathcal{N}P$-полными).

Известна $\mathcal{N}P$-полнота сотен задач. Среди них:

(Гамильтонов цикл). Имеет ли данный неориентированный граф гамильтонов цикл?

(Раскрашиваемость). Является ли данный неориентированный граф $k$-раскрашиваемым?

(Множество вершин, разрезающих контуры). Имеет ли данный ориентированный граф $k$-элементное множество вершин, разрезающих все его контуры, т. е. содержащих хотя бы по одной вершине каждого из них?

(Множество дуг, разрезающих контуры). Имеет ли данный ориентированный граф $k$-элементное множество дуг, разрезающих все его контуры, т. е. содержащих хотя бы по одной дуге каждого из них?

(Ориентированный гамильтонов цикл). Имеет ли данный ориентированный граф ориентированный гамильтонов цикл?

(Разбиение). Существует ли разбиение данного конечного множества элементов, имеющих неотрицательный вес, на два подмножества, равных по суммарному весу составляющих их элементов?

(Изоморфизм неориентированному подграфу). Содержит ли данный неориентированный граф $G$ подграф, изоморфный данному неориентированному графу $H$?

(Остовное дерево ограниченной степени). Существует ли в данном неориентированном графе остовное дерево, в котором все вершины имеют степень не более $k$?

(Минимальный эквивалентный по достижимости ориентированный граф). Можно ли удалить из данного ориентированного графа часть дуг так, чтобы отношение достижимости между вершинами не изменилось, но результирующий граф содержал бы не более $k$ дуг.

(Самый длинный путь). Имеется ли в данном неориентированном графе простой путь длины не меньше $k$?

(Доминирующее множество). Существует ли в данном неориентированном графе доминирующее множество, состоящее из не более $k$ вершин?

($3$-раскрашиваемость). Можно ли данный неориентированный граф раскрасить в три цвета?

(Нумерация графа по Гранди). Можно ли сопоставить с вершинами данного ориентированного графа $G=(V,A)$ различные неотрицательные числа таким образом, чтобы для каждого $p\in V$ число $F(p),$ сопоставленное с вершиной $p,$ совпадало с наименьшим целым числом, не принадлежащим множеству $\{F(q):q\in V,(p,q)\in A\}$?

(Минимум суммы квадратов). Может ли данное конечное множество $A$ элементов, имеющих неотрицательный размер $S(a),$ быть разбито на $k$ подмножеств $A_1,\dots ,A_k$ так, чтобы $\sum _{i=1}^k{(\sum _{a\in A_i}s(a))}^2\le t,$ где $k,t$ — заданные положительные числа?

(Расщепление множества). Существует ли разбиение данного конечного множества $A$ на два таких, что ни одно из них не содержит ни одного из элементов заданного семейства подмножеств $A$?

См. также

• Задача о вершинном покрытии,
• Задача о выполнимости,
• Задача о клике,
• Задача о неэквивалентности регулярных выражений,
• Задача о разбиении,
• Задача о точном покрытии 3-множествами,
• Задача о трехмерном сочетании,
• Классы $\mathcal{P}$ и $\mathcal{N}P$,
• Задача легко разрешимая,
• Метод локальной замены,
• Метод построения компонент,
• Задача распознавания свойств,
• Метод сужения задачи,
• Полиномиальная сводимость (трансформируемость),
• $\mathcal{N}P$-трудная задача,
• Труднорешаемая задача.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
• Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИПЦ НГУ, 2018.