Virtual Laboratory Wiki
Advertisement

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

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

Алфавитом называется всякое конечное множество символов (например, или ). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом обозначается . Языком над алфавитом называется всякое подмножество множества , то есть .

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

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

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

Сводимость по Карпу обозначается как или .

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

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

Гипотеза P ≠ NP

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

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

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

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

Примечания

  1. 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-полная задача. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Advertisement