Класс co-NP

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

Формальное определение Класс сложности co-NP определяется для множества языков, то есть множеств слов над конечным алфавитом . Язык принадлежит классу co-NP, если существует детерминированная машина Тьюринга M и некоторый полином p такие, что .

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