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

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

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

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

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

• ${\displaystyle x\in L_{1}}$ тогда и только тогда, когда ${\displaystyle f(x)\in L_{2}}$ . Сводимость по Карпу обозначается как ${\displaystyle L_{1}{\leq }_{p}L_{2}}$ или ${\displaystyle L_{1}\varpropto L_{2}}$ .

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

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

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

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

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

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

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

Гипотеза P ≠ NP

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

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

См. также

• Равенство классов P и NP

Примечания

Литература

• Гэри М., Джонсон Д. от 4 ноября 2019 на Wayback Machine . М.: Мир, 1982.
• Томас Х. Кормен и др. Глава 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 .

Ссылки

• от 6 декабря 2006 на Wayback Machine (англ.)
• от 5 декабря 2006 на Wayback Machine (англ.)