Клас 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 з іншими класами

Класи складності алгоритмів

Вважається легкими	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
Список алгоритмів