Co-NP

In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse. In ihr sind genau die Sprachen enthalten, deren Komplemente zu NP gehören. Die Klasse Co-NP besteht also aus den Sprachen, für die ein Beweis, dass ein Wort nicht zur Sprache gehört, nicht-deterministisch in polynomieller Zeit überprüft werden kann.

Formale Definitionen

Die Klasse Co-NP ist definiert als $\{L\mid {\bar {L}}\in \mathbf {NP} \}$, wobei ${\bar {L}}$ das Komplement der Sprache L bezeichnet.

Analog zu NP gibt es eine alternative Definition für Co-NP über verifizierende deterministische Turingmaschinen. Demnach ist eine Sprache L in Co-NP, genau dann, wenn es eine deterministische Turingmaschine M gibt, für welche gilt, dass

• $x\not \in L\iff \exists y\colon M(x,y)=1$,
• die Laufzeit von M(x,y) ist polynomiell beschränkt in x.

Äquivalent kann man für den ersten Punkt fordern, dass $x\in L\iff \forall y\colon M(x,y)=1$.

Eine dritte äquivalente Definition benutzt ein Berechnungsmodell welches an dem der nichtdeterministische Turingmaschine angelehnt ist. Eine Sprache L ist demnach genau dann in Co-NP, wenn es eine nichtdeterministische Turingmaschine N und ein Polynom p gibt, für die gelten:

• N hält bei Eingabe von x immer nach höchstens $p(|x|)$ Schritten.
• N akzeptiert eine Eingabe $x\in L$ genau dann, wenn alle möglichen Läufe von N bei Eingabe x akzeptieren.

Co-NP-Vollständigkeit

Analog zu anderen Komplexitätsklassen kann man innerhalb von Co-NP vollständige Probleme definieren. Hierbei nennt man eine Sprache L Co-NP-Vollständig, genau dann wenn folgende zwei Bedingungen erfüllt sind:

1. Die Sprache L ist selbst aus Co-NP.
2. Für jede Sprache L' aus Co-NP gilt: $L'\leq _{p}L$, wobei $\leq _{p}$ die Polynomialzeitreduktion beschreibt.

Wenn nur die 2. Eigenschaft erfüllt ist spricht man von Co-NP-schweren Sprachen

Die Sprache TAUTOLOGIE enthält alle Booleschen Formeln (kodiert) die bei jeder Variablenbelegung mit wahr ausgewertet werden. TAUTOLOGIE ist das Komplement von SAT und ein Beispiel einer Co-NP-vollständigen Sprache. Die Co-NP-Vollständigkeit folgt aus dem Satz von Cook und Levin. Allgemein gilt für alle NP-vollständigen Sprachen, dass deren Komplement Co-NP-vollständig ist.

Beziehung zu anderen Komplexitätsklassen

Die Komplexitätsklasse P ist eine Teilmenge von Co-NP. Die Klasse Co-NP ist wiederum in der Komplexitätsklasse PSPACE enthalten. Von beiden Teilmengenbeziehungen weiß man nicht, ob es echte Teilmengenbeziehungen sind.

Der Schnitt von NP und Co-NP enthält die Klasse P, es ist jedoch unbekannt, ob es noch weitere Sprachen in diesem Schnitt gibt.

Beziehung von Co-NP und NP

Man weiß bislang nicht wie NP und Co-NP zueinander liegen, vermutet aber, dass NP≠Co-NP. Die Klasse Co-NP ist eine Klasse in der Polynomialzeithierarchie, in welcher sie mit $\Pi _{p}^{1}$ bezeichnet wird. Falls NP=Co-NP, würde die Polynomiallzeithierarchie auf der 1. Stufe kollabieren, was bedeuten wurde, dass PH=Co-NP, jedoch wurde man in diesem Fall nichts darüber aussagen können ob P=NP. Auf der anderen Seite gilt, wenn P=NP, dann kollabiert die Polynomialzeithierarchie auf der untersten Stufe, und es würde NP=Co-NP folgen. Es ist nicht bekannt, ob aus P≠NP auch NP≠Co-NP folgt.

Wenn A eine NP-volständige Sprache ist, dann ist $A\in \mathbf {Co{\text{-}}NP}$ genau dann, wenn NP=Co-NP. Der nicht-triviale Teil der Äquivalenz kann wie folgt gezeigt werden:

$\subseteq$: Sei $L\in \mathbf {NP}$. Weil $A$ NP-schwer ist, ist $L\leq _{p}A$, und damit ${\bar {L}}\leq _{p}{\bar {A}}$. Wegen $A\in \mathbf {Co{\text{-}}NP}$ ist ${\bar {A}}\in \mathbf {NP}$, und damit ist ${\bar {L}}\in \mathbf {NP}$, also $L\in \mathbf {Co{\text{-}}NP}$.

$\supseteq$: $L\in \mathbf {Co{\text{-}}NP} \Rightarrow {\bar {L}}\in \mathbf {NP} \Rightarrow {\bar {L}}\in \mathbf {Co{\text{-}}NP} \Rightarrow {\bar {L}}\in \mathbf {NP}$.

Analog lässt sich folgender Satz zeigen: Wenn A Co-NP-vollständig ist, dann ist $A\in \mathbf {NP}$ genau dann, wenn NP=Co-NP.