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}$, если существует функция, $f:\Sigma ^{*}\to \Sigma ^{*}$, вычислимая за полиномиальное время, и обладающая следующим свойством:

• $f(x)\in L_{2}$ тогда и только тогда, когда $x\in L_{1}$.

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

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

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

Гипотеза P ≠ NP

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

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

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

Литература

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

Ссылки

• NP-полнота
• Вычислительная сложность игр и головоломок(англ.)

Классы сложности алгоритмов

 

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: NP-полная задача. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---