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 {\le}_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 лет является открытой проблемой. Научное сообщество склоняется к отрицательному ответу на этот вопрос^[1] — в этом случае решать NP-полные задачи за полиномиальное время не удастся.

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

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

См. также

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

Примечания

1. ↑ William I. Gasarch (2002). «The P=?NP poll.». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.
2. ↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate (англ.). preprint.

Литература

• Томас Х. Кормен и др. Глава 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 (англ.)

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники.

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

 

Cчитаются лёгкими	P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными	NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными	EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов