Klasa Co-NP

Klasa co-NP jest klasą dopełniającą dla problemów decyzyjnych NP. Np. dopełnieniem problemu typu "czy wszystkie elementy zbioru X spełniają warunek Y" jest "czy istnieje element zbioru X nie spełniający warunku Y".

Nie wiadomo, czy dopełnienie każdego problemu NP jest NP. Wydaje się bowiem, że czasem łatwiej pokazywać kontrprzykłady (weryfikować negatywnie) niż udowodnić prawdziwość jakiegoś twierdzenia (weryfikować pozytywnie).

Jeżeli NP != co-NP to P != NP. Implikacja w drugą stronę nie jest udowodniona.