Co-NP

In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse. In ihr sind genau die Sprachen enthalten, deren Komplement in der Klasse NP liegt. Die Klasse Co-NP besteht demnach aus den Sprachen, für die ein Beweis, dass ein Wort nicht zur Sprache gehört, in Polynomialzeit durch eine nichtdeterministische Turingmaschine ü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)=0$.

Eine dritte äquivalente Definition benutzt ein Berechnungsmodell, welches an dem der nichtdeterministischen 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.

Ein Beispiel einer Co-NP-vollständigen Sprache ist TAUTOLOGIE. TAUTOLOGIE enthält alle Booleschen Formeln die Tautologien sind, das heißt, sie werden bei jeder Variablenbelegung mit wahr ausgewertet werden. Das Komplement von SAT lässt sich auf TAUTOLOGIE reduzieren, da eine Formel genau dann nicht erfüllbar ist, wenn ihre Negation eine Tautologie ist. Das Komplement von SAT ist ein Beispiel einer Co-NP-vollständigen Sprache, was aus dem Satz von Cook und Levin geschlussfolgert werden kann. Somit lässt sich jede Sprache L' aus Co-NP auf TAUTOLOGIE reduzieren, womit die 2. Eigenschaft bewiesen ist. Weiterhin kann in Polynomialzeit verifiziert werden ob eine Variablenbelegung eine Formel nicht erfüllt und demnach ist das Komplement von TAUTOLOGIE in NP, womit auch die 1. Eigenschaft folgt. Allgemein gilt für alle NP-vollständigen Sprachen, dass ihr Komplement Co-NP-vollständig ist.

Ein deterministischer Polynomialzeitalgorithmus für ein Co-NP-vollständiges Problem würde zeigen, dass P=Co-NP und demnach wäre die Klasse Co-NP unter Komplementbildung abgeschlossen. Damit wäre das P-NP-Problem gelöst, da in diesem Fall P=NP=Co-NP gelten würde.

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 Polynomialzeithierarchie bis zur 1. Stufe kollabieren, was bedeuten würde, dass PH=Co-NP, jedoch würde 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-vollstä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 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.