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

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Формальное определение 2 Гипотеза P ≠ NP 3 Примеры NP-полных задач 4 Ссылки 5 Литература 6 Примечания 7 Ссылки

[править] Формальное определение

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

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

Язык L₁ называется сводимым (по Карпу) к языку L₂, если существует функция, , вычислимая за полиномиальное время, и обладающая следующим свойством:

• тогда и только тогда, когда .

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

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

[править] Гипотеза P ≠ NP

Основная статья: Равенство классов P и NP

Равенство классов P и NP уже более 30 лет является открытой проблемой. Научное сообщество склоняется к отрицательному решению этого вопроса — в этом случае за полиномиальное время решать NP-полные задачи не удастся.

[править] Примеры NP-полных задач

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

[править] Ссылки

• NP-полнота
• Вычислительная сложность игр и головоломок(англ.)
• Проблемы, связанные с Тетрисом Tetris is Hard, Even to Approximate, (англ.))

[править] Литература

• Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

[править] Примечания

[править] Ссылки

п·о·р NP-полные задачи
Теория сложности вычислений
Упаковка, укладка	Упаковка в контейнеры: двумерная упаковка  • линейная упаковка  • упаковка по весу  • упаковка по стоимости Задача о ранце (рюкзаке)
Булева формула	Задача выполнимости булевых формул
Коммивояжёр	Задача коммивояжёра  • Обобщённая задача коммивояжёра
Вершинное покрытие	Задача о вершинном покрытии
Клика	Задача о клике
Независимое множество	Задача о независимом множестве (наборе)
Покрытие множества	Задача о покрытии множества
Латинский квадрат	Задача о заполнении латинского квадрата
Обобщённое судоку	Задача обобщённого судоку
Какуро	Задача какуро
Пятнашки (обобщённые)	Задача поиска кратчайшего решения (костяшек более 15)
Классы сложности