NP-полная задача | это... Что такое NP-полная задача? (original) (raw)
В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Содержание
- 1 Формальное определение
- 2 Гипотеза P ≠ NP
- 3 Примеры NP-полных задач
- 4 См. также
- 5 Примечания
- 6 Литература
- 7 Ссылки
Формальное определение
Алфавитом называется всякое конечное множество символов (например, или ). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом обозначается . Языком над алфавитом называется всякое подмножество множества , то есть .
Задачей распознавания для языка называется определение того, принадлежит ли данное слово языку .
Язык называется сводимым (по Карпу) к языку , если существует функция, , вычислимая за полиномиальное время, обладающая следующим свойством:
Сводимость по Карпу обозначается как или .
Язык называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.
Таким образом, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время.
NP-полнота в сильном смысле
Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая:
- не является задачей с числовыми параметрами (т.е. максимальное значение величин, встречающихся в этой задаче ограничено сверху полиномом от длины входа),
- принадлежит классу NP,
- является NP-полной.
Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS задачи не существует псевдополиномиального алгоритма.
Гипотеза P ≠ NP
Вопрос о совпадении классов P и NP уже более 30 лет является открытой проблемой. Научное сообщество склоняется к отрицательному ответу на этот вопрос[1] — в этом случае решать NP-полные задачи за полиномиальное время не удастся.
Примеры NP-полных задач
- Задача о выполнимости булевых формул
- Кратчайшее решение «пятнашек» размера
- Задача коммивояжёра
- Проблема Штейнера
- Проблема раскраски графа
- Задача о вершинном покрытии
- Задача о покрытии множества
- Задача о клике
- Задача о независимом множестве
- Сапер (игра)
- Тетрис[2]
См. также
- Список NP-полных задач (англ.)русск.
Примечания
- ↑ William I. Gasarch (2002). «The P=?NP poll.». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.
- ↑ 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 (англ.)
NP-полные задачи | |
---|---|
Математика | |
Исследование операций:Оптимизация:Комбинаторная оптимизация | |
Максимизационная задача укладки (упаковки) | Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) |
Теория графов теория множеств | Задача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра |
Алгоритмические задачи | Задача выполнимости булевых формул (в конъюнктивной нормальной форме) |
Логические игры и головоломки | Обобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро |
См. также | Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа |
Классы сложности |