- 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
.
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 Relationund Polynome p und q gibt, sodass gilt:
- es gibt eine Turingmaschine, die bei Eingabe (x,y) in Zeit q(x,y) entscheidet, ob
ist und
genau dann, wenn es ein y gibt mit
und
.
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
und
- für Eingaben
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
. Tatsächlich gilt folgender Satz: Wenn A NP-vollständig ist, dann ist
genau dann, wenn
. Der nicht-triviale Teil der Äquivalenz kann wie folgt gezeigt werden:
: Sei
. Weil A NP-schwer ist, ist
, und damit
. Wegen
ist
, und damit ist
, also
.
:
Ganz analog lässt sich folgender Satz zeigen: Wenn A Co-NP-vollständig ist, dann istgenau dann, wenn
.
Weil P unter Komplement abgeschlossen ist, gilt folgender Satz: Wenn, dann
. 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
).
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
) möglich ist, zu entscheiden, ob eine vorgelegte Zahl prim ist oder nicht. Der AKS-Primzahltest liefert jedoch keine Primfaktorzerlegung.
- es gibt eine Turingmaschine, die bei Eingabe (x,y) in Zeit q(x,y) entscheidet, ob
Wikimedia Foundation.