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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.