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

---

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 ^{*}}$, вычислимая за полиномиальное время, обладающая следующим свойством:

---