Класс co-NP

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

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

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

Отношения класса NP с другими классами

Классы сложности алгоритмов