В теорії алгоритмів часто розглядається клас, тісно пов'язаний з 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 з іншими класами


Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP (co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів