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>H</math>?

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

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

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

(''[[Минимальный эквивалентный по  достижимости  ориентированный

граф]]''). Можно ли удалить из данного ориентированного графа

часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами

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

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

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

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

в три цвета?

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

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

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

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

''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Задача легко разрешимая]], [[Метод локальной замены]], [[Метод построения компонент]], [[Задача распознавания свойств]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].''