Co-NP

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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, deterministisch in Polynomialzeit durch eine Turingmaschine überprüft werden kann.

Formale Definitionen[Bearbeiten]

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

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

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[Bearbeiten]

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. TAUTOLOGIE lässt sich auf das Komplement von SAT 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. Demnach ist auch TAUTOLOGIE Co-NP-vollständig. Allgemein gilt für alle NP-vollständigen Sprachen, dass ihr Komplement Co-NP-vollständig ist.

Ein Polynomialzeit–Algorithmus 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[Bearbeiten]

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[Bearbeiten]

Man weiß bislang nicht wie NP und Co-NP zueinander liegen, vermutet aber, dass NPCo-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.[2] 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 PNP auch NPCo-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.

Belege[Bearbeiten]

  1. Boaz Barak: NP completeness,CoNP, the Polynomial Hierarchy and P/poly (lecture notes) (pdf; 174 kB) Abgerufen am 26. April 2013.
  2. Sanjeev Arora, Boaz Barak: Computational Complexity. Cambridge University Press, , ISBN 978-0-521-42426-4, S. 57.