Als co-NP-vollständig werden in der Komplexitätstheorie diejenigen Probleme bezeichnet, die zu den schwierigsten Problemen der Komplexitätsklasse co-NP gehören. Jedes Problem in co-NP lässt sich mit höchstens polynomiellem Aufwand auf ein co-NP-vollständiges Problem reduzieren. Gilt P ungleich co-NP, so sind alle co-NP-vollständigen Probleme nicht in deterministischer Polynomialzeit lösbar. Existiert hingegen ein effizienter Algorithmus zur Lösung eines co-NP-vollständigen Problems, so kann dieser verwendet werden, um sämtliche Probleme in co-NP effizient zu lösen.
Dieses Konzept ist insbesondere im Zusammenhang mit dem P-NP-Problem sowie der NP-Vollständigkeit von Interesse. Siehe co-NP und NP-Vollständigkeit für weitere Details.
Definition Ein Entscheidungsproblem C ist co-NP-vollständig, wenn es in co-NP liegt und wenn jedes Problem aus co-NP in polynomieller Zeit auf C reduziert werden kann. Dies bedeutet, dass es für jedes co-NP-Problem L einen Algorithmus in Polynomialzeit gibt, der jede Instanz von L in eine Instanz von C überführt, sodass beide Instanzen denselben Wahrheitswert besitzen. Als Konsequenz gilt: Wenn ein Polynomialzeitalgorithmus für C existiert, könnten alle co-NP-Probleme in Polynomialzeit gelöst werden.
Das Konzept der co-NP-Vollständigkeit unterscheidet sich nicht wesentlich von dem der NP-Vollständigkeit, da jedes Problem aus NP trivial in ein Problem aus co-NP überführt werden kann und umgekehrt, indem „Akzeptieren“ und „Verwerfen“ vertauscht werden. Folglich kann jedes NP-vollständiges Problem in ein co-NP-vollständiges Problem umgewandelt werden.
Da sowohl die Frage des P-NP-Problems als auch die Frage, ob NP=co-NP gilt, offen ist, ist insbesondere nicht bekannt, ob eine echte Obermenge von P ist. Für alle bisher bekannten Probleme in sind polynomielle Algorithmen bekannt, sie liegen also in P.
Beispiele Ein Beispiel für ein co-NP-vollständiges Problem ist das Überprüfen von Tautologien, also das Problem zu entscheiden, ob eine gegebene boolesche Formel eine Tautologie ist; das heißt, ob jede mögliche Belegung der Variablen mit Wahrheitswerten zu einer wahren Aussage führt. Dies ist das Komplement des Problems der booleschen Erfüllbarkeit, das fragt, ob es mindestens eine solche Belegung gibt und NP-vollständig ist. Konkret gilt:
Ist eine Formel keine Tautologie, so kann dies durch eine explizite Belegung in Polynomialzeit widerlegt werden. Ist eine Formel erfüllbar, so kann dies durch eine explizite Belegung in Polynomialzeit bewiesen werden.
Falls eine spärliche Sprache (engl. sparse language, d. h. eine Sprache, deren Anzahl von Strings pro Längenklasse polynomial beschränkt ist) co-NP-vollständig oder sogar nur co-NP-schwer ist, folgt daraus P=NP. Dieses Resultat wird im Theorem von Mahaney verwendet.
Einzelnachweise
Kategorie:Komplexitätsklasse