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

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

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

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

Задачей распознавания для языка $L$ называется определение того, принадлежит ли данное слово языку $L$.

Пусть $L_{1}$ и $L_{2}$ - два языка над алфавитом $\Sigma$. Язык $L_{1}$ называется сводимым (по Карпу) к языку $L_{2}$, если существует функция, $f:\Sigma ^{*}\to \Sigma ^{*}$, вычислимая за полиномиальное время, обладающая следующим свойством:

• $x\in L_{1}$ тогда и только тогда, когда $f(x)\in L_{2}$. Сводимость по Карпу обозначается как $L_{1}{\leq }_{p}L_{2}$ или $L_{1}\varpropto L_{2}$.

Язык $L_{2}$ называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.

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

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

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

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

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

Гипотеза P ≠ NP

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

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

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

• Задача о выполнимости булевых формул
• Кратчайшее решение «пятнашек» размера $n\times n$
• Задача коммивояжёра
• Проблема Штейнера
• Проблема раскраски графа
• Задача о вершинном покрытии
• Задача о покрытии множества
• Задача о клике
• Задача о независимом множестве
• Сапер (игра)
• Тетрис

См. также

• Список NP-полных задач

Литература

• Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки

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