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

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

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

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

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

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

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

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

Неформально говоря, то что задача $A$ сводится к задаче $B$ , означает, что задача $A$ «не сложнее» задачи $B$ (так как, если мы можем решить $B$ , то можем решить и $A$ ). Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).

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

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

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

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

Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS-задачи не существует псевдополиномиального алгоритма^{[источник не указан 2798 дней]}.

Гипотеза P ≠ NP

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

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

См. также

Равенство классов P и NP

Примечания

↑ William I. Gasarch. The P=?NP poll. (неопр.) // SIGACT News. — 2002. — Т. 33, № 2. — С. 34—47. — doi:10.1145/1052796.1052804.
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate (англ.). preprint.

Литература

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи Архивная копия от 4 ноября 2019 на Wayback Machine. М.: Мир, 1982.
Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 0-07-013151-1.
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.

Ссылки

NP-полнота
Вычислительная сложность игр и головоломок Архивная копия от 6 декабря 2006 на Wayback Machine (англ.)
A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann Архивная копия от 5 декабря 2006 на Wayback Machine (англ.)

[1] William I. Gasarch. The P=?NP poll. (неопр.) // SIGACT News. — 2002. — Т. 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.

[1]

[2]

Классы сложности алгоритмов
Считаются лёгкими	DLOGTIME^[англ.] AC⁰^[англ.] ACC⁰^[англ.] TC⁰^[англ.] L SL^[англ.] RL^[англ.] NL NC SC^[англ.] CC^[англ.] P P-complete^[англ.] ZPP RP BPP BQP EQP APX
Предполагаются сложными	UP^[англ.] NP NP-complete co-NP co-NP-complete AM^[англ.] MA^[англ.] QMA PH ⊕P^[англ.] PP #P #P-complete^[англ.] IP^[англ.] PSPACE PSPACE-complete^[англ.]
Считаются сложными	EXPTIME NEXPTIME^[англ.] EXPSPACE^[англ.] 2-EXPTIME^[англ.] ELEMENTARY^[англ.] R PR^[англ.] RE^[англ.] RE-complete^[англ.] Co-RE^[англ.] Co-RE-complete^[англ.] ALL^[англ.]

NP-полные задачи
Максимизационная задача укладки (упаковки)	Упаковка в контейнеры двумерная упаковка линейная упаковка упаковка по весу упаковка по стоимости Задача о рюкзаке
Теория графов теория множеств	Задача о вершинном покрытии Задача о клике Задача о независимом множестве (наборе) Задача о покрытии множества Задача Штейнера Задача коммивояжёра Обобщённая задача коммивояжёра
Алгоритмические задачи	Задача выполнимости булевых формул (в конъюнктивной нормальной форме)
Логические игры и головоломки	Обобщённые пятнашки (игра в N²-1) задача поиска кратчайшего решения Задачи, решения которых применяются в Тетрис Задача обобщённого судоку Задача о заполнении латинского квадрата Задача какуро
Классы сложности Исследование операций Оптимизация Комбинаторная оптимизация Прикладная математика Теория алгоритмов Динамическое программирование 21 NP-полная задача Карпа