Informatik

Was ist die Komplexitätsklasse co-NP?

co-NP enthält Probleme, deren Nein-Instanzen polynomiell überprüfbare Zertifikate haben.

Äquivalent: $L\in\text{co-NP}$ genau dann, wenn das Komplement von $L$ in $NP$ liegt.