Класс NP-complete

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

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

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

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

Язык L₁ называется сводимым (по Карпу) к языку L₂, если существует функция, $f: \Sigma^* \to \Sigma^*$, вычислимая за полиномиальное время, и обладающая следующим свойством:

• $f(x)\in L_2$ тогда и только тогда, когда $x\in L_1$.

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

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

Гипотеза P ≠ NP

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

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

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

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

Ссылки

• NP-полнота
• Вычислительная сложность игр и головоломок(англ.)
• Проблемы, связанные с Тетрисом Tetris is Hard, Even to Approximate, (англ.))

Литература

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

Примечания

Ссылки

Классы сложности

P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PP • PCP • IP • PH