Co-NP - co-NP
In der Berechnungskomplexitätstheorie ist co-NP eine Komplexitätsklasse . Ein Entscheidungsproblem X ist genau dann ein Mitglied von co-NP, wenn sein Komplement X in der Komplexitätsklasse NP liegt . Die Klasse kann wie folgt definiert werden: Ein Entscheidungsproblem liegt in co-NP genau dann vor, wenn nur keine Instanzen ein " Zertifikat " mit polynomialer Länge haben und es einen polynomialen Algorithmus gibt, der verwendet werden kann, um jedes angebliche Zertifikat zu verifizieren.
Das heißt, co-NP ist die Menge von Entscheidungsproblemen, bei denen es ein Polynom p(n) und eine polynomialzeitbeschränkte Turingmaschine M gibt, so dass für jede Instanz x , x genau dann eine Nein- Instanz ist, wenn: für einige mögliches Zertifikat c der Länge durch p(n) begrenzt , akzeptiert die Turingmaschine M das Paar ( x , c ).
Komplementäre Probleme
Während ein NP-Problem fragt, ob eine gegebene Instanz eine Ja- Instanz ist , fragt sein Komplement , ob eine Instanz eine Nein- Instanz ist , was bedeutet, dass das Komplement in co-NP ist. Jede Ja- Instanz für das ursprüngliche NP-Problem wird zu einer Nein- Instanz für sein Komplement und umgekehrt.
Unerfüllbarkeit
Ein Beispiel für ein NP-vollständiges Problem ist das Boolesche Erfüllbarkeitsproblem : Ist eine gegebene Boolesche Formel erfüllbar (gibt es eine mögliche Eingabe, für die die Formel wahr ausgibt)? Das komplementäre Problem fragt: "Ist eine Boolesche Formel gegeben, ist sie nicht erfüllbar (geben alle möglichen Eingaben für die Formel falsch aus)?". Da dies die Ergänzung des Erfüllbarkeitsproblems ist, ist ein Zertifikat für eine Nein- Instanz dasselbe wie für eine Ja- Instanz aus dem ursprünglichen NP-Problem: eine Menge boolescher Variablenzuweisungen, die die Formel wahr machen. Andererseits wäre ein Zertifikat einer Ja- Instanz für das Komplementärproblem genauso komplex wie die Nein- Instanz des ursprünglichen NP-Erfüllbarkeitsproblems.
Doppelprobleme
co-NP-Vollständigkeit
Ein Problem L ist genau dann co-NP-vollständig, wenn L in co-NP liegt und für jedes Problem in co-NP eine Polynomialzeitreduktion von diesem Problem auf L existiert .
Tautologie-Reduktion
Die Bestimmung, ob eine Formel in der Aussagenlogik eine Tautologie ist, ist co-NP-vollständig, dh ob die Formel unter jeder möglichen Zuordnung zu ihren Variablen als wahr bewertet wird.
Beziehung zu anderen Klassen
P , die Klasse der polynomial zeitlösbaren Probleme, ist eine Teilmenge von NP und co-NP. P wird in beiden Fällen als strikte Teilmenge angesehen (und kann nachweislich in einem Fall nicht streng und im anderen nicht streng sein).
NP und Co-NP werden auch als ungleich angesehen. Wenn ja, dann kann kein NP-vollständiges Problem in co-NP und kein co-NP-vollständiges Problem in NP sein. Dies kann wie folgt gezeigt werden. Angenommen aus Gründen des Widerspruchs gibt es ein NP-vollständiges Problem X , das in co-NP liegt. Da alle Probleme in NP auf X reduziert werden können , folgt daraus, dass wir für jedes Problem in NP eine nichtdeterministische Turingmaschine konstruieren können , die ihr Komplement in polynomieller Zeit entscheidet; dh NP co-NP. Daraus folgt, dass die Menge der Komplemente der Probleme in NP eine Teilmenge der Menge der Komplemente der Probleme in co-NP ist; dh co-NP NP. Somit ist co-NP = NP. Der Beweis, dass kein co-NP-vollständiges Problem in NP liegen kann, wenn NP ≠ co-NP symmetrisch ist.
Faktorisierung ganzer Zahlen
Ein Beispiel für ein Problem, von dem bekannt ist, dass es sowohl zu NP als auch zu co-NP gehört (aber nicht in P bekannt ist), ist die Faktorisierung ganzer Zahlen: Bestimmen Sie bei gegebenen positiven ganzen Zahlen m und n , ob m einen Faktor kleiner als n und größer als eins hat . Die Mitgliedschaft in NP ist klar; wenn m einen solchen Faktor hat, dann ist der Faktor selbst ein Zertifikat. Die Zugehörigkeit zu co-NP ist ebenfalls unkompliziert: Man kann einfach die Primfaktoren von m auflisten , die alle größer oder gleich n sind , deren Gültigkeit der Verifizierer durch Multiplikation und den AKS-Primalitätstest bestätigen kann . Es ist derzeit nicht bekannt, ob es einen Polynomialzeitalgorithmus für die Faktorisierung gibt, äquivalent dazu, dass die ganzzahlige Faktorisierung in P ist, und daher ist dieses Beispiel als eines der natürlichsten Probleme interessant, die in NP und co-NP bekannt sind, aber nicht bekannt sind in P sein