Класс co-NP

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формальное определение[править | править вики-текст]

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

Отношения класса NP с другими классами[править | править вики-текст]