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

Взаимоотношение между классами P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если P≠NP и если P=NP

NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

Формальное определение

Алфавитом называется всякое конечное множество символов (например, {[math]\displaystyle{ {0,1} }[/math]} или {[math]\displaystyle{ {a,b,c} }[/math]}). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом [math]\displaystyle{ \Sigma }[/math] обозначается [math]\displaystyle{ \Sigma^* }[/math]. Языком [math]\displaystyle{ L }[/math] над алфавитом [math]\displaystyle{ \Sigma }[/math] называется всякое подмножество множества [math]\displaystyle{ \Sigma^* }[/math], то есть [math]\displaystyle{ L\subset\Sigma^* }[/math].

Задачей распознавания для языка [math]\displaystyle{ L }[/math] называется определение того, принадлежит ли данное слово языку [math]\displaystyle{ L }[/math].

Пусть [math]\displaystyle{ L_1 }[/math] и [math]\displaystyle{ L_2 }[/math] — два языка над алфавитом [math]\displaystyle{ \Sigma }[/math]. Язык [math]\displaystyle{ L_1 }[/math] называется сводимым (по Карпу) к языку [math]\displaystyle{ L_2 }[/math], если существует функция, [math]\displaystyle{ f\colon \Sigma^* \to \Sigma^* }[/math], вычислимая за полиномиальное время, обладающая следующим свойством:

• [math]\displaystyle{ x\in L_1 }[/math] тогда и только тогда, когда [math]\displaystyle{ f(x)\in L_2 }[/math]. Сводимость по Карпу обозначается как [math]\displaystyle{ L_1 {\le}_p L_2 }[/math] или [math]\displaystyle{ L_1 \varpropto L_2 }[/math].

Язык [math]\displaystyle{ L_2 }[/math] называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.

Неформально говоря, то что задача [math]\displaystyle{ A }[/math] сводится к задаче [math]\displaystyle{ B }[/math], означает, что задача [math]\displaystyle{ A }[/math] «не сложнее» задачи [math]\displaystyle{ B }[/math] (так как, если мы можем решить [math]\displaystyle{ B }[/math], то можем решить и [math]\displaystyle{ A }[/math]). Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).

Из определения следует, что, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время.

NP-полнота в сильном смысле

Основная статья: NP-полнота в сильном смысле

Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая:

1. не является задачей с числовыми параметрами (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)
2. является NP-полной.

Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS-задачи не существует псевдополиномиального алгоритма.

Гипотеза P ≠ NP

Основная статья: Равенство классов P и NP

Вопрос о совпадении классов P и NP уже более тридцати лет является одной из центральных открытых проблем. Научное сообщество склоняется к отрицательному ответу на этот вопрос — в этом случае решать NP-полные задачи за полиномиальное время не удастся.

Примеры NP-полных задач

Основная статья: Список NP-полных задач

• Задача о выполнимости булевых формул
• Задача коммивояжёра
• Задача о вершинном покрытии
• Задача о покрытии множества
• Задача о независимом множестве
• Задача о клике
• Проблема Штейнера
• Проблема раскраски графа
• Пятнашки
• Судоку
• Сапёр
• Тетрис

См. также

• Равенство классов P и NP

Литература

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи Архивная копия от 4 ноября 2019 на Wayback Machine. М.: Мир, 1982.
• Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 0-07-013151-1.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.

Ссылки

• NP-полнота
• Вычислительная сложность игр и головоломок Архивная копия от 6 декабря 2006 на Wayback Machine (англ.)
• A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann Архивная копия от 5 декабря 2006 на Wayback Machine (англ.)