В теорії алгоритмів часто розглядається клас, тісно пов'язаний з P і NP, - клас доповнень мов з NP, званий co-NP.
Формальне визначення
Клас складності co-NP визначається для безлічі мов, тобто множин слів над кінцевим алфавітом . Мова
належить класу co-NP, якщо існує детермінована машина Тьюринга M і деякий поліном p такі, що
.