NP-полная задача: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Строка 7: Строка 7:
'''Задачей распознавания''' для языка <math>L</math> называется определение того, принадлежит ли данное слово языку <math>L</math>.
'''Задачей распознавания''' для языка <math>L</math> называется определение того, принадлежит ли данное слово языку <math>L</math>.


Пусть <math>L_1</math> и <math>L_2</math> — два языка над алфавитом <math>\Sigma</math>. Язык <math>L_1</math> называется [[Сведение по Карпу|сводимым (по Карпу)]] к языку <math>L_2</math>, если существует [[функция (математика)|функция]], <math>f: \Sigma^* \to \Sigma^*</math>, вычислимая за [[класс P|полиномиальное время]], обладающая следующим свойством:
Пусть <math>L_1</math> и <math>L_2</math> — два языка над алфавитом <math>\Sigma</math>. Язык <math>L_1</math> называется [[Сведение по Карпу|сводимым (по Карпу)]] к языку <math>L_2</math>, если существует [[функция (математика)|функция]], <math>f\colon \Sigma^* \to \Sigma^*</math>, вычислимая за [[класс P|полиномиальное время]], обладающая следующим свойством:
* <math>x\in L_1 </math> тогда и только тогда, когда <math>f(x)\in L_2</math>. Сводимость по Карпу обозначается как <math>L_1 {\le}_p L_2</math> или <math>L_1 \varpropto L_2</math>.
* <math>x\in L_1 </math> тогда и только тогда, когда <math>f(x)\in L_2</math>. Сводимость по Карпу обозначается как <math>L_1 {\le}_p L_2</math> или <math>L_1 \varpropto L_2</math>.


Версия от 18:27, 15 июня 2018

Взаимотношение между классами P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если P≠NP и если P=NP

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

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

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

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

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

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

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

Неформально говоря, то что задача сводится к задаче , означает, что задача «не сложнее» задачи (так как, если мы можем решить , то можем решить и ). Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).

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

NP-полнота в сильном смысле

В другом языковом разделе есть более полная статья Strong NP-completeness (англ.).

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

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

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

Гипотеза P ≠ NP

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

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

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

См. также

Примечания

  1. ↑ William I. Gasarch (2002). "The P=?NP poll" (PDF). 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.
  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.

Ссылки


Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=NP-полная_задача&oldid=93347313