Klasa Co-NP

Klasa Co-NP – klasa złożoności dopełniająca dla problemów decyzyjnych NP. Przykładowo dopełnieniem problemu typu „czy wszystkie elementy zbioru X spełniają warunek Y” jest „czy istnieje element zbioru X niespeł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).

Wykazano, że jeżeli NP ≠ Co-NP, to P ≠ NP. Jednak implikacja w drugą stronę nie została udowodniona.