coNP
Sei
eine Komplexitätsklasse
besteht aus allen Sprachen
, deren Komplement 
in liegt.
Für alle deterministischen Komplexitätsklassen gilt
also z.B.
, da sich die Ausgabe einfach vertauschen läßt.
Dies läßt sich für nichtdeterministische Sprachen nicht durchführen, da das ,,Raten'' der Belegung nicht mitspielt. Wir können zum Beispiel das komplementäre Problem von
konstruieren, daß immer dann ,,JA'' zurückgibt, wenn die eigegebene Formel nicht erfüllbar ist und ,,NEIN'' zurückgibt, wenn sie erfüllbar ist. Schmeißen wir nun unser ,,Orakel'' an, so gibt es uns eine Belegung, wo die Formel nicht erfüllbar ist, falls es eine gibt. Wir wissen dann jedoch nicht, ob die Formel für alle Belegungen unerfüllbar ist. Wir können also mit der einfachen Umkehr des Verfahrens kein korrektes Verfahren bekommen.