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

Взаимоотношение между классами P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если P≠NP и если P=NP

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

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

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

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

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

• $x\in L_1$ тогда и только тогда, когда $f(x)\in L_2$. Сводимость по Карпу обозначается как $L_1{\le }_p{L}_2$ или $L_1\propto L_2$.

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

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

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

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

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

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

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

Гипотеза P ≠ NP

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

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

• Задача о выполнимости булевых формул
• Задача коммивояжёра
• Задача о вершинном покрытии
• Задача о покрытии множества
• Задача о независимом множестве
• Задача о клике
• Проблема Штейнера
• Проблема раскраски графа
• Пятнашки
• Судоку
• Сапёр
• Тетрис
• Кубик-змейка

См. также

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

Литература

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи Шаблон:Wayback. М.: Мир, 1982.
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• NP-полнота
• Вычислительная сложность игр и головоломок Шаблон:WaybackШаблон:Ref-en
• A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann Шаблон:WaybackШаблон:Ref-en