Quelltext der Seite Co-NP

In der [[Komplexitätstheorie]] bezeichnet '''Co-NP''' eine [[Komplexitätsklasse]]. In ihr sind genau die Sprachen enthalten, deren [[Komplement (Mengenlehre)|Komplement]] in der Klasse [[NP (Komplexitätsklasse)|'''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 <math>\{ L \mid  \bar L \in \mathbf{NP}\}</math>, wobei <math>\bar L</math> das Komplement der Sprache ''L''
bezeichnet.

Analog zu '''NP''' gibt es eine alternative Definition für '''Co-NP''' über verifizierende deterministische [[Turingmaschine]]n. Demnach
ist eine Sprache ''L'' in '''Co-NP''', genau dann, wenn es eine deterministische Turingmaschine ''M'' gibt,
für welche gilt, dass
* <math> x\not\in L \iff \exists y\colon M(x,y)=1</math>,
* die Laufzeit von ''M(x,y)'' ist [[Polynomialzeit|polynomiell beschränkt]] in ''x''.
Äquivalent kann man für den ersten Punkt fordern, dass <math> x\in L \iff \forall y\colon M(x,y)=0</math>.<ref>
{{cite web | url=https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf | format=pdf; 174&nbsp;kB | first=Boaz | last=Barak | title=NP completeness,CoNP, the Polynomial Hierarchy and P/poly (lecture notes) | accessdate=2013-04-26}}</ref>

Eine dritte äquivalente Definition benutzt ein Berechnungsmodell, welches an dem der [[Nichtdeterministische Turingmaschine|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 <math>p(|x|)</math> Schritten.
* ''N'' akzeptiert eine Eingabe <math>x \in L</math> 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ändigkeit (Komplexitätstheorie)|vollständige]]
Probleme definieren. Hierbei nennt man eine Sprache ''L'' '''Co-NP'''-vollständig, genau dann wenn folgende zwei Bedingungen erfüllt sind:
# Die Sprache ''L'' ist selbst aus '''Co-NP'''.
# Für jede Sprache ''L' '' aus '''Co-NP''' gilt: <math>L' \leq_p L</math>, wobei <math>\leq_p</math> 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 [[Boolesche Algebra|Booleschen Formeln]] die [[Tautologie (Logik)|Tautologie]]n sind, das heißt, sie werden bei jeder Variablenbelegung mit wahr ausgewertet werden. Das Komplement von [[Erfüllbarkeitsproblem der Aussagenlogik|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ändigkeit|'''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 (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 Teilmenge]]nbeziehungen 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 <math>\Pi_p^1</math> bezeichnet wird. Falls '''NP'''='''Co-NP''', würde die Polynomialzeithierarchie bis zur 1. Stufe kollabieren, was bedeuten würde, dass [[Polynomialzeithierarchie|'''PH''']]='''Co-NP''', jedoch würde man in diesem Fall nichts darüber aussagen können ob '''P'''='''NP'''.<ref>
{{cite book  |first=Sanjeev | last=Arora | coauthors=Boaz Barak  | title=Computational Complexity | publisher=Cambridge University Press | isbn= 978-0-521-42426-4 | pages=57}} </ref>
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ändigkeit|'''NP'''-vollständige Sprache]] ist, dann ist <math>A\in \mathbf{Co\text{-}NP}</math> genau dann, wenn '''NP'''='''Co-NP'''. Der nicht-triviale Teil der Äquivalenz kann wie folgt gezeigt werden:
: <math>\subseteq</math>: Sei <math>L\in\mathbf{NP}</math>. Weil <math>A</math> [[NP-Schwere|'''NP'''-schwer]] ist, ist <math>L\leq_p A</math>, und damit <math>\bar{L} \leq_p \bar A</math>. Wegen <math>A\in\mathbf{Co\text{-}NP}</math> ist <math>\bar A\in\mathbf{NP}</math>, und damit ist <math>\bar L\in\mathbf{NP}</math>, also <math>L\in\mathbf{Co\text{-}NP}</math>.
: <math>\supseteq</math>: <math>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}</math>.

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

== Belege ==
<references />

{{DEFAULTSORT:Conp}}
[[Kategorie:Komplexitätsklasse]]