Klasa Co-NP
Z Wikipedii, wolnej encyklopedii
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
