Класс сo-NP

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

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

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

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

Классы сложности

P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PP • PCP • IP • PH