Класс co-NP

В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, — класс дополнений языков из NP, называемый co-NP.

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

Класс сложности co-NP определяется для множества языков, то есть множеств слов над конечным алфавитом $\mathrm{\Sigma }$. Язык $L\subseteq {\mathrm{\Sigma }}^{*}$ принадлежит классу co-NP, если существует детерминированная машина Тьюринга M и некоторый полином p такие, что $L=\{x\in {\mathrm{\Sigma }}^{*}:\mathrm{\forall }y,|y|<p(|x|)M(x,y)=0\}$.

Литература

• Шаблон:Книга
• Шаблон:Книга