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

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

Алфавитом называется всякое конечное множество символов (например, или ). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом обозначается . Языком над алфавитом называется всякое подмножество множества , то есть .

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

Язык называется сводимым (по Карпу) к языку , если существует функция, , вычислимая за полиномиальное время, обладающая следующим свойством:

• тогда и только тогда, когда

Сводимость по Карпу обозначается как или .

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

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

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

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

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

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

Гипотеза P ≠ NP

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

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

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

См. также

• Список NP-полных задач (англ.)русск.

Примечания