Co-NP

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, deterministisch in polynomieller Zeit überprüft werden kann.

Zum Beispiel ist Subset Sum ein NP-vollständiges Problem. Gefragt ist, ob es in einer endlichen Menge ganzer Zahlen eine nichtleere Teilmenge gibt, deren Elemente c als Summe haben. Das Gegenstück in Co-NP ist die Frage, ob alle nichtleeren Teilmengen nicht c als Summe haben.

Formale Definition

Gemäß der obengenannten Beschreibung ergibt CoNP := \{L | L^{\rm C}\in NP\}.


Analog zu NP lässt sich Co-NP auch über deterministische Turingmaschinen definieren, die einen Beweis verifizieren oder falsifizieren. Damit ergibt sich folgende äquivalente Definition für Co-NP: Eine Sprache L ist genau dann in Co-NP, wenn es eine Relation R_L \subseteq \{0,1\}^* \times \{0,1\}^* und Polynome p und q gibt, sodass gilt:

  • es gibt eine Turingmaschine, die bei Eingabe (x,y) in Zeit q(x,y) entscheidet, ob (x, y) \in R_L ist und
  • x \notin L genau dann, wenn es ein y gibt mit |y| \leq p(|x|) und (x, y) \in R_L.


Außerdem ist eine Sprache L genau dann in Co-NP, wenn es eine nichtdeterministische Turingmaschine M und ein Polynom p mit den folgenden Eigenschaften gibt:

  • M hält bei Eingabe von x immer nach höchstens p( | x | ) Schritten,
  • M akzeptiert jede Eingabe x \in L und
  • für Eingaben x \notin L gibt es mindestens einen Lauf, so dass x von M verworfen wird.

Diese Definition ergibt sich sofort aus der ersten und der Sprachakzeptanz-Definition für NP.

Beziehung zu anderen Komplexitätsklassen

P ist eine Teilmenge von sowohl NP als auch Co-NP. Es wird angenommen, dass in beiden Fällen eine echte Teilmengenbeziehung vorliegt. Man vermutet außerdem, dass \mathbf{NP}\neq\mathbf{CoNP}. Tatsächlich gilt folgender Satz: Wenn A NP-vollständig ist, dann ist A\in\mathbf{CoNP} genau dann, wenn \mathbf{NP}=\mathbf{CoNP}. 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_pA, und damit L^{\mathrm{C}}\leq_pA^{\mathrm{C}}. Wegen A\in\mathbf{CoNP} ist A^{\mathrm{C}}\in\mathbf{NP}, und damit ist L^{\mathrm{C}}\in\mathbf{NP}, also L\in\mathbf{CoNP}.
\supseteq: L\in\mathbf{CoNP} \Rightarrow L^{\mathrm{C}}\in\mathbf{NP} \Rightarrow L^{\mathrm{C}}\in\mathbf{CoNP} \Rightarrow (L^{\mathrm{C}})^{\mathrm{C}}=L \in\mathbf{NP}


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


Weil P unter Komplement abgeschlossen ist, gilt folgender Satz: Wenn \mathbf{P}=\mathbf{NP}, dann \mathbf{NP}=\mathbf{CoNP}. Ob hiervon auch die Umkehrung gilt, ist unbekannt.

Wenn ein Problem sowohl in NP als auch in Co-NP enthalten ist, so wird allgemein angenommen, dass es nicht NP-vollständig ist (da ansonsten \mathbf{NP} = \mathbf{CoNP}).

Primzahltest

Lange Zeit wurde vermutet, dass Primalität im Durchschnitt von NP und Co-NP liegt, aber nicht zu P gehört.

2002 wurde von Manindra Agrawal, Neeraj Kayal und Nitin Saxena der Beweis erbracht, dass es in polynomieller Zeit (genauer in \mathbf{O}((\log n)^{12})) möglich ist, zu entscheiden, ob eine vorgelegte Zahl prim ist oder nicht. Der AKS-Primzahltest liefert jedoch keine Primfaktorzerlegung.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”