4635
правок
NP-Полная задача: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>\mathcal NP</math>-Полная задача''' (''[[NP-Complete problem|<math>\mathcal NP</math>-Complete problem]]'') | '''<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>\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>{\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- | [[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> вершин? | ||
(''[[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>\,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> | \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- | * ''[[Задача о вершинном покрытии]],'' | ||
* ''[[Задача о выполнимости]],'' | |||
* ''[[Задача о клике]],'' | |||
* ''[[Задача о неэквивалентности регулярных выражений]],'' | |||
* ''[[Задача о разбиении]],'' | |||
* ''[[Задача о точном покрытии 3-множествами]],'' | |||
* ''[[Задача о трехмерном сочетании]],'' | |||
* ''[[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]],'' | |||
* ''[[Задача легко разрешимая]],'' | |||
* ''[[Метод локальной замены]],'' | |||
* ''[[Метод построения компонент]],'' | |||
* ''[[Задача распознавания свойств]],'' | |||
* ''[[Метод сужения задачи]],'' | |||
* ''[[Полиномиальная сводимость (трансформируемость)]],'' | |||
* ''[[NP-Трудная задача|<math>\mathcal NP</math>-трудная задача]],'' | |||
* ''[[Труднорешаемая задача]].'' | |||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||