NP-полная задача
NP-полная задача — в
Формальное определение
(например, {} или {}). Множество всех возможных
Задачей распознавания для языка называется определение того, принадлежит ли данное слово языку .
Пусть и — два языка над алфавитом . Язык называется
- тогда и только тогда, когда . Сводимость по Карпу обозначается как или .
Язык называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.
Неформально говоря, то что задача сводится к задаче , означает, что задача «не сложнее» задачи (так как, если мы можем решить , то можем решить и ). Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).
Из определения следует, что, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время.
NP-полнота в сильном смысле
Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая:
- не является задачей с числовыми параметрами (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)
- является NP-полной.
Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS-задачи не существует псевдополиномиального алгоритма[источник не указан 2536 дней].
Гипотеза P ≠ NP
Вопрос о совпадении классов P и NP уже более тридцати лет является одной из центральных
Примеры NP-полных задач
- Задача о выполнимости булевых формул
- Задача коммивояжёра
- Задача о вершинном покрытии
- Задача о покрытии множества
- Задача о независимом множестве
- Задача о клике
- Проблема Штейнера
- Проблема раскраски графа
- Пятнашки
- Судоку
- Сапёр
- Тетрис[2]
- Кубик-змейка[3]
См. также
Примечания
- 15 июня 2007 года.
- ↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate (англ.). preprint.
- ↑ Abel, Z.; Demaine, E.D.; Demaine, M.L.; Eisenstat, S.; Lynch, J.; Schardl, T.B. (2013). "Finding a Hamiltonian Path in a Cube with Specified Turns is Hard". Journal of Information Processing. 21 (3): 368—377. Архивировано 5 декабря 2023. Дата обращения: 5 декабря 2023.
Литература
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи Архивная копия от 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 (англ.)