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

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

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

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

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

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

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

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

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

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

NP-полнота в сильном смысле[править | править вики-текст]

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

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. William I. Gasarch (2002). «The P=?NP poll.». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.
  2. 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.

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