NP-Полная задача: различия между версиями

'''<math>\mathcal NP</math>-Полная задача''' (''[[NP-Complete problem|<math>\mathcal NP</math>-Complete problem]]'') — такая задача <math>\,A</math> из класса <math>\mathcal NP</math> всех задач,

недетерминированно разрешимых за полиномиальное время, что любая задача из <math>\mathcal NP</math> ''[[полиномиальная сводимость (трансформируемость)|полиномиально сводится]]'' к <math>\,A.</math> Если требование принадлежности <math>\,A</math> классу <math>\mathcal NP</math> не

рассматривается, то используется термин ''<math>\mathcal NP</math>-трудная'' задача.

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

<math>{\mathcal NP}</math>-полные задачи являются "самыми трудными" в классе <math>{\mathcal NP}.</math>

Если какая-нибудь <math>{\mathcal NP}</math>-полная задача может быть решена за полиномиальное время, то и любая задача из <math>{\mathcal NP}</math> полиномиально разрешима, а если какая-то задача из <math>{\mathcal NP}</math> труднорешаема, то и любая <math>{\mathcal NP}</math>-полная задача является труднорешаемой. При этом, для того чтобы доказать <math>{\mathcal NP}</math>-полноту некоторой задачи из <math>{\mathcal NP},</math> достаточно показать, что какая-то из

<math>{\mathcal NP}</math>-полных задач полиномиально сводится к ней.

Вопрос о взаимоотношении классов <math>{\mathcal P}</math> и <math>{\mathcal NP}</math> имеет

<math>{\mathcal P}\subseteq {\mathcal NP}</math> и если <math>L\in {\mathcal NP},</math> то существует такой полином <math>\,p(n)</math> и ''ДМТ'' <math>\,M,</math> что <math>\,L</math> допускается на <math>\,M</math> с [[временная сложность|временной сложностью]] <math>\,O(2^{p(n)}).</math> Однако до сих пор не доказано, содержит класс <math>{\mathcal NP}</math> труднорешаемые задачи или нет, т. е. <math>{\mathcal NP\setminus P}\neq \emptyset</math> или <math>{\mathcal NP=P}.</math> Вместе с тем известно, что в предположении <math>{\mathcal P}\neq {\mathcal NP}</math> класс <math>{\mathcal NP}</math> не просто содержит два непересекающихся подкласса: класс <math>{\mathcal P}</math> и класс <math>{\mathcal NP}</math>-полных задач, а также должен включать задачи, не принадлежащие ни одному из этих подклассов (т.е. при <math>{\mathcal P}\neq

{\mathcal NP}</math> должны существовать задачи из <math>{\mathcal NP},</math> которые

неразрешимы за полиномиальное время и не являются <math>{\mathcal NP}</math>-полными).

Известна <math>{\mathcal NP}</math>-полнота сотен задач.

(''[[Гамильтонов цикл]]'').

Имеет ли данный [[неориентированный граф]] гамильтонов цикл?

[[k-Раскрашиваемый граф|<math>\,k</math>-раскрашиваемым]]?

(''[[Множество вершин, разрезающих контуры]]''). Имеет ли данный

[[ориентированный граф]] <math>\,k</math>-элементное множество вершин, ''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной вершине каждого из них?

(''[[Множество дуг, разрезающих контуры]]''). Имеет ли данный

ориентированный граф <math>\,k</math>-элементное множество дуг,

''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной

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

(''[[Разбиение]]'').

(''[[Изоморфизм неориентированному подграфу]]''). Содержит ли данный

неориентированный граф <math>\,G</math>

[[подграф]], изоморфный данному неориентированному графу <math>\,H</math>?

(''[[Остовное дерево ограниченной степени]]''). Существует ли в данном

неориентированном графе [[остовное дерево]], в котором все [[вершина|вершины]] имеют

[[степень вершины|степень]] не более <math>\,k</math>?

(''Минимальный эквивалентный по  достижимости  ориентированный'' ''граф).'' Можно ли удалить из данного ориентированного графа часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами

<math>\,k</math> дуг.

(''[[Самый длинный путь]]''). Имеется ли в данном неориентированном графе

[[простой путь]] [[длина пути|длины]] не меньше <math>\,k</math>?

(''[[Доминирующее множество]]''). Существует ли в данном неориентированном

графе доминирующее множество, состоящее из не более <math>\,k</math> вершин?

(''[[3-Раскрашиваемость|<math>\,3</math>-раскрашиваемость]]''). Можно ли данный неориентированный граф раскрасить

в три цвета?

(''[[Нумерация графа по Гранди]]''). Можно ли сопоставить с вершинами данного

ориентированного графа <math>\,G=(V,A)</math> различные неотрицательные числа таким

образом, чтобы для каждого <math>\,p\in V</math> число <math>\,F(p),</math> сопоставленное с

вершиной <math>\,p,</math> совпадало с наименьшим целым числом, не принадлежащим

(''[[Минимум суммы квадратов]]''). Может ли данное конечное множество <math>\,A</math>

элементов, имеющих неотрицательный размер <math>\,S(a),</math> быть разбито на <math>\,k</math>

подмножеств <math>\,A_1,\ldots, A_k</math> так, чтобы <math>\,\sum^{k}_{i=1}\left(

\sum_{a\in A_i} s(a)\right)^2\leq t,</math> где <math>\,k,t</math> — заданные

(''[[Расщепление множества]]''). Существует ли разбиение данного конечного

множества <math>\,A</math> на два таких, что ни одно из них не содержит ни одного

из элементов заданного семейства подмножеств <math>\,A</math>?

==См. также ==

* ''[[Задача о вершинном покрытии]],''

* ''[[Задача о выполнимости]],''

* ''[[Задача о клике]],''

* ''[[Задача о неэквивалентности регулярных выражений]],''

* ''[[Задача о разбиении]],''

* ''[[Задача о точном покрытии 3-множествами]],''

* ''[[Задача о трехмерном сочетании]],''

* ''[[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]],''

* ''[[Задача легко разрешимая]],''

* ''[[Метод локальной замены]],''

* ''[[Метод построения компонент]],''

* ''[[Задача распознавания свойств]],''

* ''[[Метод сужения задачи]],''

* ''[[Полиномиальная сводимость (трансформируемость)]],''

* ''[[NP-Трудная задача|<math>\mathcal NP</math>-трудная задача]],''

* ''[[Труднорешаемая задача]].''

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

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

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