Класс 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 с другими классами[править | править вики-текст]