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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''<math>\mathcal NP</math>-Полная задача''' (''[[NP-Complete problem|<math>\mathcal NP</math>-Complete problem]]'') - такая задача <math>A</math> из класса <math>\mathcal NP</math> всех задач,
'''<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>\,A.</math> Если требование принадлежности <math>\,A</math> классу <math>\mathcal NP</math> не
рассматривается, то используется термин ''<math>\mathcal NP</math>-трудная'' задача.
рассматривается, то используется термин ''<math>\mathcal NP</math>-трудная'' задача.


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


Строка 23: Строка 23:
(''Раскрашиваемость'').
(''Раскрашиваемость'').
Является ли данный неориентированный граф
Является ли данный неориентированный граф
[[k-раскрашиваемый граф|<math>k</math>-раскрашиваемым]]?
[[k-Раскрашиваемый граф|<math>\,k</math>-раскрашиваемым]]?


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


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


(''[[Изоморфизм неориентированному подграфу]]''). Содержит ли данный
(''[[Изоморфизм неориентированному подграфу]]''). Содержит ли данный
неориентированный граф <math>G</math>
неориентированный граф <math>\,G</math>
[[подграф]], изоморфный данному неориентированному графу <math>H</math>?
[[подграф]], изоморфный данному неориентированному графу <math>\,H</math>?


(''[[Остовное дерево ограниченной степени]]''). Существует ли в данном
(''[[Остовное дерево ограниченной степени]]''). Существует ли в данном
неориентированном графе [[остовное дерево]], в котором все [[вершина|вершины]] имеют
неориентированном графе [[остовное дерево]], в котором все [[вершина|вершины]] имеют
[[степень вершины|степень]] не более <math>k</math>?
[[степень вершины|степень]] не более <math>\,k</math>?


(''[[Минимальный эквивалентный по  достижимости  ориентированный
(''[[Минимальный эквивалентный по  достижимости  ориентированный
Строка 53: Строка 53:
часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами
часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами
не изменилось, но результирующий граф содержал бы не более
не изменилось, но результирующий граф содержал бы не более
<math>k</math> дуг.
<math>\,k</math> дуг.


(''[[Самый длинный путь]]''). Имеется ли в данном неориентированном графе
(''[[Самый длинный путь]]''). Имеется ли в данном неориентированном графе
[[простой путь]] [[длин пути|длины]] не меньше <math>k</math>?
[[простой путь]] [[длина пути|длины]] не меньше <math>\,k</math>?


(''[[Доминирующее множество]]''). Существует ли в данном неориентированном
(''[[Доминирующее множество]]''). Существует ли в данном неориентированном
графе доминирующее множество, состоящее из не более <math>k</math> вершин?
графе доминирующее множество, состоящее из не более <math>\,k</math> вершин?


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


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


(''[[Минимум суммы квадратов]]''). Может ли данное конечное множество <math>A</math>
(''[[Минимум суммы квадратов]]''). Может ли данное конечное множество <math>\,A</math>
элементов, имеющих неотрицательный размер <math>S(a)</math>, быть разбито на <math>k</math>
элементов, имеющих неотрицательный размер <math>\,S(a),</math> быть разбито на <math>\,k</math>
подмножеств <math>A_1,\ldots, A_k</math> так, чтобы <math>\sum^{k}_{i=1}\left(
подмножеств <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> --- заданные
\sum_{a\in A_i} s(a)\right)^2\leq t,</math> где <math>\,k,t</math> заданные
положительные числа?
положительные числа?


(''[[Расщепление множества]]''). Существует ли разбиение данного конечного
(''[[Расщепление множества]]''). Существует ли разбиение данного конечного
множества <math>A</math> на два таких, что ни одно из них не содержит ни одного
множества <math>\,A</math> на два таких, что ни одно из них не содержит ни одного
из элементов заданного семейства подмножеств <math>A</math>?
из элементов заданного семейства подмножеств <math>\,A</math>?


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


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


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

Текущая версия от 12:29, 10 июня 2011

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

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

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


Известна [math]\displaystyle{ {\mathcal NP} }[/math]-полнота сотен задач. Среди них:

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

(Раскрашиваемость). Является ли данный неориентированный граф [math]\displaystyle{ \,k }[/math]-раскрашиваемым?

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

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

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

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

(Изоморфизм неориентированному подграфу). Содержит ли данный неориентированный граф [math]\displaystyle{ \,G }[/math] подграф, изоморфный данному неориентированному графу [math]\displaystyle{ \,H }[/math]?

(Остовное дерево ограниченной степени). Существует ли в данном неориентированном графе остовное дерево, в котором все вершины имеют степень не более [math]\displaystyle{ \,k }[/math]?

([[Минимальный эквивалентный по достижимости ориентированный граф]]). Можно ли удалить из данного ориентированного графа часть дуг так, чтобы отношение достижимости между вершинами не изменилось, но результирующий граф содержал бы не более [math]\displaystyle{ \,k }[/math] дуг.

(Самый длинный путь). Имеется ли в данном неориентированном графе простой путь длины не меньше [math]\displaystyle{ \,k }[/math]?

(Доминирующее множество). Существует ли в данном неориентированном графе доминирующее множество, состоящее из не более [math]\displaystyle{ \,k }[/math] вершин?

([math]\displaystyle{ \,3 }[/math]-раскрашиваемость). Можно ли данный неориентированный граф раскрасить в три цвета?

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

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

(Расщепление множества). Существует ли разбиение данного конечного множества [math]\displaystyle{ \,A }[/math] на два таких, что ни одно из них не содержит ни одного из элементов заданного семейства подмножеств [math]\displaystyle{ \,A }[/math]?

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.