In der rechenbetonten Kompliziertheitstheorie ist co-NP eine Kompliziertheitsklasse. Ein Problem ist ein Mitglied von co-NP, wenn, und nur wenn seine Ergänzung in der Kompliziertheitsklasse NP ist. In einfachen Begriffen ist co-NP die Klasse von Problemen, für die effizient nachprüfbare Beweise keiner Beispiele, manchmal genannt Gegenbeispiele, bestehen.

Ein Beispiel eines NP-complete Problems ist das Teilmenge-Summe-Problem: In Anbetracht eines begrenzten Satzes von ganzen Zahlen ist dort eine nichtleere Teilmenge die resümiert zur Null? Um einen Beweis von "ja" Beispiel zu geben, muss man eine nichtleere Teilmenge angeben, die wirklich zur Null resümiert. Das Ergänzungsproblem ist in co-NP und fragt: "In Anbetracht eines begrenzten Satzes von ganzen Zahlen hat jede nichtleere Teilmenge eine Nichtnullsumme?" Um einen Beweis von "nein" zu geben, führen als Beispiel an man muss eine nichtleere Teilmenge angeben, die wirklich zur Null resümiert, die leicht nachgeprüft wird.

P, die Klasse der polynomischen Zeit lösbare Probleme, ist eine Teilmenge sowohl von NP als auch von co-NP. Wie man denkt, ist P eine strenge Teilmenge in beiden Fällen (und kann beweisbar in einem Fall, aber nicht dem anderen nicht streng sein). Wie man auch denkt, sind NP und co-NP ungleich. Wenn so, dann kann kein NP-complete Problem in co-NP sein, und kein co-NP-complete Problem kann in NP sein.

Das kann wie folgt gezeigt werden. Nehmen Sie an, dass es ein NP-complete Problem gibt, das in co-NP ist. Da alle Probleme in NP auf dieses Problem reduziert werden können, hieraus folgt dass für alle Probleme in NP wir eine nichtdeterministische Maschine von Turing bauen können, die die Ergänzung des Problems in der polynomischen Zeit entscheidet, d. h. NP ist eine Teilmenge von co-NP. Davon, hieraus folgt dass der Satz von Ergänzungen der Probleme in NP eine Teilmenge des Satzes von Ergänzungen der Probleme in co-NP ist, d. h., ist co-NP eine Teilmenge von NP. Seitdem wir bereits gewusst haben, dass NP eine Teilmenge von co-NP ist, hieraus folgt dass sie dasselbe sind. Der Beweis für die Tatsache, dass kein co-NP-complete Problem in NP sein kann, ist symmetrisch.

Wenn, wie man zeigen kann, ein Problem sowohl in NP als auch in co-NP ist, der allgemein als starke Beweise akzeptiert wird, dass das Problem wahrscheinlich nicht NP-complete (seit sonst NP = co-NP) ist.

Ein Beispiel eines Problems, das, wie man bekannt, in NP und in co-NP ist, ist ganze Zahl factorization: In Anbetracht positiver ganzer Zahlen bestimmen M und n, ob M einen Faktor weniger hat als n und größer als einer. Die Mitgliedschaft in NP ist klar; wenn M wirklich solch einen Faktor dann hat, ist der Faktor selbst ein Zertifikat. Die Mitgliedschaft in co-NP ist auch aufrichtig: Man kann gerade die Hauptfaktoren der M verzeichnen, die der verifier bestätigen kann, um durch die Multiplikation und den AKS primality Test gültig zu sein.

Ganze Zahl factorization ist häufig mit dem nah zusammenhängenden primality Problem verwirrt. Wie man lange bekannt hat, sind sowohl Primality-Prüfung als auch factorization NP und co-NP Probleme gewesen. Der AKS primality Test, veröffentlicht 2002, beweist, dass primality, der auch prüft, in P liegt, während factorization kann oder keinen polynomisch-maligen Algorithmus haben kann.

Außenverbindungen