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

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

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

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

Назовём языком множество слов над алфавитом $Σ$ . Задачей здесь является определение того, принадлежит данное слово языку или нет. Язык $L 1$ называется сводимым (по Карпу) к языку $L 2$ , если существует функция, $f: \Sigma^* \to \Sigma^*$ , вычислимая за полиномиальное время, обладающая следующим свойством: f(x) принадлежит $L 2$ тогда и только тогда, когда x принадлежит $L 1$ . Язык $L 2$ называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден и при этом сам лежит в классе NP. Таким образом, если будет найден алгоритм, решающий хоть одну NP-полную задачу за полиномиальное время, все NP-задачи будут лежать в классе P.

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

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