NP-Vollständigkeit

Beim booleschen Erfüllbarkeitsproblem (SAT) geht es darum, zu bestimmen, ob eine aussagenlogische Formel (siehe Beispiel) durch eine geeignete Zuordnung von Wahrheitswerten zu ihren Variablen wahr gemacht werden kann. Es ist zwar leicht zu überprüfen, ob eine gegebene Zuordnung die Formel wahr macht, aber es ist keine wesentlich schnellere Methode bekannt, eine zufriedenstellende Zuordnung zu finden, als alle Zuordnungen nacheinander auszuprobieren. Cook und Levin haben bewiesen, dass jedes einfach zu überprüfende Problem genauso schnell gelöst werden kann wie SAT, das somit NP-komplett ist. ⓘ

In der Komplexitätstheorie ist ein Problem NP-komplett, wenn:

1. es ein Problem ist, für das die Korrektheit jeder Lösung schnell (d.h. in polynomieller Zeit) überprüft werden kann und ein Brute-Force-Suchalgorithmus eine Lösung finden kann, indem er alle möglichen Lösungen ausprobiert.
2. das Problem kann zur Simulation jedes anderen Problems verwendet werden, für das wir schnell überprüfen können, ob eine Lösung korrekt ist. In diesem Sinne sind NP-komplette Probleme die schwierigsten der Probleme, deren Lösungen schnell verifiziert werden können. Wenn wir schnell Lösungen für ein NP-komplettes Problem finden können, können wir auch schnell die Lösungen für jedes andere Problem finden, für das eine gegebene Lösung leicht verifiziert werden kann. ⓘ

Der Name "NP-vollständig" ist eine Abkürzung für "nicht-deterministisch polynomial-zeitvollständig". In dieser Bezeichnung bezieht sich "nicht-deterministisch" auf nicht-deterministische Turing-Maschinen, eine Möglichkeit, die Idee eines Brute-Force-Suchalgorithmus mathematisch zu formalisieren. Polynomialzeit bezieht sich auf eine Zeitspanne, die für einen deterministischen Algorithmus zur Überprüfung einer einzelnen Lösung oder für eine nichtdeterministische Turing-Maschine zur Durchführung der gesamten Suche als "schnell" angesehen wird. "Vollständig" bezieht sich auf die Eigenschaft, alles in derselben Komplexitätsklasse simulieren zu können. ⓘ

Genauer gesagt sollte jede Eingabe des Problems mit einer Menge von Lösungen polynomialer Länge verbunden sein, deren Gültigkeit schnell (in polynomialer Zeit) getestet werden kann, so dass die Ausgabe für jede Eingabe "ja" ist, wenn die Lösungsmenge nicht leer ist, und "nein", wenn sie leer ist. Die Komplexitätsklasse von Problemen dieser Form wird NP genannt, eine Abkürzung für "nondeterministische Polynomialzeit". Ein Problem wird als NP-hart bezeichnet, wenn alles, was in NP ist, in polynomieller Zeit in das Problem transformiert werden kann, auch wenn es nicht in NP ist. Umgekehrt ist ein Problem NP-komplett, wenn es sowohl in NP als auch NP-schwer ist. Die NP-kompletten Probleme stellen die schwersten Probleme in NP dar. Wenn ein NP-komplettes Problem einen Polynomialzeit-Algorithmus hat, dann haben alle Probleme in NP einen. Die Menge der NP-kompletten Probleme wird oft mit NP-C oder NPC bezeichnet. ⓘ

Obwohl eine Lösung für ein NP-komplettes Problem "schnell" verifiziert werden kann, gibt es keine bekannte Möglichkeit, eine Lösung schnell zu finden. Das heißt, dass die Zeit, die zur Lösung des Problems mit jedem derzeit bekannten Algorithmus benötigt wird, mit der Größe des Problems rapide zunimmt. Folglich ist die Frage, ob es möglich ist, diese Probleme schnell zu lösen, das so genannte P-versus-NP-Problem, eines der grundlegenden ungelösten Probleme der heutigen Informatik. ⓘ

Obwohl eine Methode zur schnellen Berechnung von Lösungen für NP-komplette Probleme noch nicht entdeckt wurde, stoßen Informatiker und Programmierer immer noch häufig auf NP-komplette Probleme. NP-komplette Probleme werden oft mit heuristischen Methoden und Näherungsalgorithmen angegangen. ⓘ

Formal wird NP-Vollständigkeit nur für Entscheidungsprobleme definiert (mögliche Lösungen nur „ja“ oder „nein“), während man bei anderen Problemtypen von NP-Äquivalenz spricht (etwa bei Suchproblemen oder Optimierungsproblemen). Umgangssprachlich wird diese Unterscheidung jedoch oft nicht vollzogen, so dass man ganz allgemein von „NP-vollständigen Problemen“ spricht, unabhängig davon, ob ein Entscheidungsproblem vorliegt oder nicht. Dies ist möglich, da verschiedene Problemtypen ineinander überführbar (aufeinander reduzierbar) sind. ⓘ

Seit der Einführung der NP-Vollständigkeit durch Cook wurde die Vollständigkeit zu einem allgemeinen Konzept für beliebige Komplexitätsklassen ausgebaut. ⓘ

Überblick

NP-komplette Probleme gehören zu NP, der Menge aller Entscheidungsprobleme, deren Lösungen in polynomialer Zeit verifiziert werden können; NP kann auch als die Menge der Entscheidungsprobleme definiert werden, die in polynomialer Zeit auf einer nichtdeterministischen Turing-Maschine gelöst werden können. Ein Problem p in NP ist NP-komplett, wenn jedes andere Problem in NP in polynomialer Zeit in p transformiert (oder reduziert) werden kann. ⓘ

Es ist nicht bekannt, ob jedes Problem in NP schnell gelöst werden kann - dies wird als P versus NP-Problem bezeichnet. Aber wenn jedes NP-komplette Problem schnell gelöst werden kann, dann kann es auch jedes Problem in NP, denn die Definition eines NP-kompletten Problems besagt, dass jedes Problem in NP schnell auf jedes NP-komplette Problem reduzierbar sein muss (d.h. es kann in Polynomialzeit reduziert werden). Aus diesem Grund wird oft gesagt, dass NP-komplette Probleme schwieriger oder schwieriger sind als NP-Probleme im Allgemeinen. ⓘ

Formale Definition

Ein Entscheidungsproblem $\scriptstyle C$ ist NP-komplett, wenn:

1. $\scriptstyle C$ in NP ist, und
2. Jedes Problem in NP ist reduzierbar auf $\scriptstyle C$ in polynomieller Zeit reduzierbar ist. ⓘ

$\scriptstyle C$ kann gezeigt werden, dass es in NP ist, indem man zeigt, dass eine Kandidatenlösung für $\scriptstyle C$ in polynomialer Zeit verifiziert werden kann. ⓘ

Man beachte, dass ein Problem, das die Bedingung 2 erfüllt, als NP-hart gilt, unabhängig davon, ob es die Bedingung 1 erfüllt oder nicht. ⓘ

Eine Konsequenz dieser Definition ist, dass wir, wenn wir einen Polynomialzeit-Algorithmus (auf einer UTM oder einer anderen Turing-äquivalenten abstrakten Maschine) für $\scriptstyle C$hätten, könnten wir alle Probleme in NP in polynomialer Zeit lösen. ⓘ

Hintergrund

Euler-Diagramm für P, NP, NP-komplette und NP-harte Problemmengen. Die linke Seite gilt unter der Annahme, dass P≠NP ist, während die rechte Seite unter der Annahme gilt, dass P=NP ist (mit der Ausnahme, dass die leere Sprache und ihr Komplement nie NP-komplett sind und im Allgemeinen nicht jedes Problem in P oder NP NP-komplett ist). ⓘ

Das Konzept der NP-Vollständigkeit wurde 1971 eingeführt (siehe Cook-Levin-Theorem), obwohl der Begriff NP-komplett erst später eingeführt wurde. Auf der STOC-Konferenz 1971 gab es eine heftige Debatte zwischen den Informatikern darüber, ob NP-komplette Probleme in polynomieller Zeit auf einer deterministischen Turing-Maschine gelöst werden können. John Hopcroft brachte alle Teilnehmer der Konferenz dazu, sich darauf zu einigen, dass die Frage, ob NP-komplette Probleme in polynomieller Zeit lösbar sind, auf einen späteren Zeitpunkt verschoben werden sollte, da niemand formale Beweise für die eine oder andere Behauptung hatte. Dies ist bekannt als "die Frage, ob P=NP". ⓘ

Niemand konnte bisher schlüssig feststellen, ob NP-komplette Probleme tatsächlich in polynomieller Zeit lösbar sind, was dieses Problem zu einem der großen ungelösten Probleme der Mathematik macht. Das Clay Mathematics Institute setzt eine Belohnung von 1 Million US-Dollar für denjenigen aus, der einen formalen Beweis dafür erbringt, dass P=NP oder dass P≠NP ist. ⓘ

Die Existenz von NP-kompletten Problemen ist nicht offensichtlich. Das Cook-Levin-Theorem besagt, dass das boolesche Erfüllbarkeitsproblem NP-komplett ist, und beweist damit, dass es solche Probleme gibt. Im Jahr 1972 bewies Richard Karp, dass mehrere andere Probleme ebenfalls NP-komplett sind (siehe Karps 21 NP-komplette Probleme); es gibt also eine Klasse von NP-kompletten Problemen (neben dem Booleschen Erfüllbarkeitsproblem). Seit den ursprünglichen Ergebnissen haben sich Tausende anderer Probleme durch Reduktionen von anderen Problemen, die sich zuvor als NP-komplett erwiesen hatten, als NP-komplett erwiesen; viele dieser Probleme sind in dem Buch Computers and Intractability von Garey und Johnson aus dem Jahr 1979 gesammelt: A Guide to the Theory of NP-Completeness. ⓘ

Der Begriff der NP-Vollständigkeit wurde 1971 von Stephen A. Cook in seinem heute so genannten Satz von Cook eingeführt. Darin zeigte er, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist. Heute existieren deutlich einfachere konstruktive Nachweise für die Existenz solcher Probleme, allerdings sind die dafür verwendeten Sprachen sehr künstlich. Cooks Verdienst besteht also auch darin, für eine besonders interessante Sprache diesen Nachweis erbracht zu haben. ⓘ

NP-komplette Probleme

Einige NP-komplette Probleme mit Angabe der Reduktionen, die typischerweise verwendet werden, um ihre NP-Vollständigkeit zu beweisen ⓘ

Der einfachste Weg zu beweisen, dass ein neues Problem NP-komplett ist, ist zunächst zu beweisen, dass es in NP liegt, und dann ein bekanntes NP-komplettes Problem darauf zu reduzieren. Daher ist es nützlich, eine Vielzahl von NP-kompletten Problemen zu kennen. Die folgende Liste enthält einige bekannte Probleme, die NP-komplett sind, wenn sie als Entscheidungsprobleme ausgedrückt werden.

• Boolesches Erfüllbarkeitsproblem (SAT)
• Knapsack-Problem
• Hamilton'sches Pfadproblem
• Travelling-Salesman-Problem (Entscheidungsversion)
• Subgraph-Isomorphie-Problem
• Teilmengen-Summen-Problem
• Cliquen-Problem
• Vertex-Cover-Problem
• Problem der unabhängigen Menge
• Problem der dominierenden Menge
• Graphenfärbungsproblem ⓘ

Rechts sehen Sie ein Diagramm einiger Probleme und der Reduktionen, die typischerweise verwendet werden, um ihre NP-Vollständigkeit zu beweisen. In diesem Diagramm werden die Probleme von unten nach oben reduziert. Beachten Sie, dass dieses Diagramm als Beschreibung der mathematischen Beziehung zwischen diesen Problemen irreführend ist, da es eine Polynomialzeitreduktion zwischen zwei beliebigen NP-kompletten Problemen gibt; es zeigt jedoch an, wo der Nachweis dieser Polynomialzeitreduktion am einfachsten war. ⓘ

Oft gibt es nur einen kleinen Unterschied zwischen einem Problem in P und einem NP-kompletten Problem. Zum Beispiel bleibt das 3-Zufriedenheits-Problem, eine Einschränkung des Booleschen Zufriedenheits-Problems, NP-komplett, während das etwas eingeschränktere 2-Zufriedenheits-Problem in P ist (genauer gesagt, es ist NL-komplett), aber das etwas allgemeinere max. 2-sat. Problem ist wiederum NP-komplett. Die Bestimmung, ob ein Graph mit 2 Farben gefärbt werden kann, ist in P, aber mit 3 Farben ist es NP-komplett, selbst wenn man es auf planare Graphen beschränkt. Die Bestimmung, ob ein Graph ein Zyklus oder bipartit ist, ist sehr einfach (in L), aber das Finden eines maximalen bipartiten oder eines maximalen Zyklus-Untergraphen ist NP-komplett. Eine Lösung des Knapsack-Problems innerhalb eines festen Prozentsatzes der optimalen Lösung kann in polynomieller Zeit berechnet werden, aber die Suche nach der optimalen Lösung ist NP-komplett. ⓘ

Intermediäre Probleme

Ein interessantes Beispiel ist das Graphen-Isomorphismus-Problem, ein Problem der Graphentheorie, bei dem es darum geht, zu bestimmen, ob zwischen zwei Graphen ein Graphen-Isomorphismus besteht. Zwei Graphen sind isomorph, wenn der eine in den anderen umgewandelt werden kann, indem man einfach die Eckpunkte umbenennt. Betrachten Sie diese beiden Probleme:

• Graphenisomorphismus: Ist der Graph G₁ isomorph zum Graph G₂?
• Untergraphen-Isomorphismus: Ist der Graph G₁ isomorph zu einem Untergraphen des Graphen G₂? ⓘ

Das Subgraph-Isomorphismus-Problem ist NP-komplett. Es wird vermutet, dass das Graphen-Isomorphismus-Problem weder in P noch NP-komplett ist, obwohl es in NP liegt. Dies ist ein Beispiel für ein Problem, das als schwer, aber nicht als NP-komplett gilt. Diese Klasse wird als NP-Zwischenprobleme bezeichnet und existiert nur dann, wenn P≠NP. ⓘ

Lösen von NP-kompletten Problemen

Gegenwärtig benötigen alle bekannten Algorithmen für NP-komplette Probleme Zeit, die superpolynomial zur Eingabegröße ist, und zwar exponentiell zu $O(n^{k})$ für einige $k>0$ und es ist unbekannt, ob es noch schnellere Algorithmen gibt. ⓘ

Die folgenden Techniken können zur Lösung von Rechenproblemen im Allgemeinen angewandt werden, und sie führen oft zu wesentlich schnelleren Algorithmen:

• Approximation: Anstatt nach einer optimalen Lösung zu suchen, suchen Sie nach einer Lösung, die höchstens um einen Faktor von einer optimalen Lösung entfernt ist.
• Randomisierung: Verwenden Sie Zufälligkeit, um eine schnellere durchschnittliche Laufzeit zu erhalten, und lassen Sie den Algorithmus mit einer kleinen Wahrscheinlichkeit scheitern. Hinweis: Die Monte-Carlo-Methode ist kein Beispiel für einen effizienten Algorithmus in diesem speziellen Sinne, obwohl evolutionäre Ansätze wie genetische Algorithmen dies sein können.
• Einschränkung: Durch Einschränkung der Eingabestruktur (z. B. auf planare Graphen) sind in der Regel schnellere Algorithmen möglich.
• Parametrisierung: Oft gibt es schnelle Algorithmen, wenn bestimmte Parameter der Eingabe festgelegt werden.
• Heuristik: Ein Algorithmus, der in vielen Fällen "einigermaßen gut" funktioniert, für den es aber keinen Beweis dafür gibt, dass er immer schnell ist und immer ein gutes Ergebnis liefert. Häufig werden metaheuristische Ansätze verwendet. ⓘ

Ein Beispiel für einen heuristischen Algorithmus ist ein suboptimaler $\scriptstyle O(n\log n)$ Ein Beispiel für einen heuristischen Algorithmus ist ein suboptimaler Greedy-Coloring-Algorithmus, der für das Graph-Coloring in der Phase der Registerzuweisung einiger Compiler verwendet wird, eine Technik, die als Graph-Coloring Global Register Allocation bezeichnet wird. Jeder Scheitelpunkt ist eine Variable, Kanten werden zwischen Variablen gezeichnet, die gleichzeitig verwendet werden, und die Farben zeigen das Register an, das jeder Variablen zugewiesen ist. Da die meisten RISC-Maschinen über eine ziemlich große Anzahl von Allzweckregistern verfügen, ist selbst ein heuristischer Ansatz für diese Anwendung effektiv. ⓘ

Vollständigkeit unter verschiedenen Arten der Reduktion

In der obigen Definition von NP-Vollständigkeit wurde der Begriff Reduktion in der technischen Bedeutung einer polynomialzeitlichen Many-One-Reduktion verwendet. ⓘ

Eine andere Art der Reduktion ist die Polynomialzeit-Turing-Reduktion. Ein Problem $\scriptstyle X$ ist polynomial-zeitlich Turing-reduzierbar auf ein Problem $\scriptstyle Y$ wenn bei einem Unterprogramm, das die Aufgabe $\scriptstyle Y$ in Polynomialzeit löst, man ein Programm schreiben kann, das dieses Unterprogramm aufruft und das Problem $\scriptstyle X$ in polynomieller Zeit löst. Dies steht im Gegensatz zur Many-One-Reduzierbarkeit, die die Einschränkung hat, dass das Programm das Unterprogramm nur einmal aufrufen kann, und der Rückgabewert des Unterprogramms muss der Rückgabewert des Programms sein. ⓘ

Wenn man das Analogon zu NP-vollständig mit Turing-Reduktionen anstelle von Many-One-Reduktionen definiert, wird die resultierende Problemmenge nicht kleiner als NP-vollständig; es ist eine offene Frage, ob sie noch größer wird. ⓘ

Eine andere Art von Reduktion, die ebenfalls oft zur Definition von NP-Vollständigkeit verwendet wird, ist die logarithmische Raum-Vielfach-Reduktion, d.h. eine Vielfach-Reduktion, die nur mit einer logarithmischen Menge an Raum berechnet werden kann. Da jede Berechnung, die im logarithmischen Raum durchgeführt werden kann, auch in polynomialer Zeit durchgeführt werden kann, folgt daraus, dass, wenn es eine logarithmische Raum-Mannigfaltigkeitsreduktion gibt, es auch eine polynomiale Mannigfaltigkeitsreduktion gibt. Diese Art der Reduktion ist raffinierter als die übliche Polynomialzeit-Vieleins-Reduktion und erlaubt es uns, weitere Klassen wie P-komplett zu unterscheiden. Ob sich die Definition von NP-vollständig unter dieser Art von Reduktionen ändert, ist noch ein offenes Problem. Alle derzeit bekannten NP-kompletten Probleme sind NP-komplett unter log space Reduktionen. Alle derzeit bekannten NP-kompletten Probleme bleiben auch unter viel schwächeren Reduktionen wie $AC_{0}$ Kürzungen und $NC_{0}$ Reduktionen. Einige NP-komplette Probleme wie SAT sind bekanntlich sogar unter polylogarithmischen Zeitprojektionen vollständig. Es ist jedoch bekannt, dass AC⁰-Reduktionen eine strikt kleinere Klasse definieren als Polynomialzeit-Reduktionen. ⓘ

Benennung

Laut Donald Knuth wurde der Name "NP-complete" von Alfred Aho, John Hopcroft und Jeffrey Ullman in ihrem berühmten Lehrbuch "The Design and Analysis of Computer Algorithms" populär gemacht. Er berichtet, dass sie die Änderung in den Druckfahnen des Buches (von "polynomial-complete") in Übereinstimmung mit den Ergebnissen einer von ihm durchgeführten Umfrage in der theoretischen Computerwissenschaft eingeführt haben. Andere Vorschläge, die in der Umfrage gemacht wurden, waren "Herkules", "formidable", Steiglitz' "hard-boiled" zu Ehren von Cook und Shen Lins Akronym "PET", das für "probably exponential time" stand, aber je nachdem, wie sich das P-gegen-NP-Problem entwickelte, auch für "provably exponential time" oder "previously exponential time" stehen konnte. ⓘ

Häufige Missverständnisse

Die folgenden Missverständnisse sind häufig.

• "NP-komplette Probleme sind die schwierigsten bekannten Probleme." Da NP-komplette Probleme in NP sind, ist ihre Laufzeit höchstens exponentiell. Es ist jedoch bewiesen, dass einige Probleme mehr Zeit benötigen, z. B. die Presburger Arithmetik. Für einige Probleme wurde sogar bewiesen, dass sie überhaupt nicht gelöst werden können, z. B. das Halting-Problem.
• "NP-komplette Probleme sind schwierig, weil es so viele verschiedene Lösungen gibt". Einerseits gibt es viele Probleme, die einen ebenso großen Lösungsraum haben, aber in polynomieller Zeit gelöst werden können (z. B. Minimum Spanning Tree). Andererseits gibt es NP-Probleme mit höchstens einer Lösung, die unter randomisierter Polynomialzeit-Reduktion NP-schwer sind (siehe Valiant-Vazirani-Theorem).
• "Das Lösen von NP-kompletten Problemen erfordert exponentielle Zeit." Erstens würde dies implizieren, dass P ≠ NP ist, was immer noch eine ungelöste Frage ist. Außerdem gibt es für einige NP-komplette Probleme tatsächlich Algorithmen, die in superpolynomieller, aber subexponentieller Zeit laufen, wie z. B. O(2^√nn). Beispielsweise sind die Probleme der unabhängigen Menge und der dominierenden Menge für planare Graphen NP-komplett, können aber in subexponentieller Zeit mit Hilfe des planaren Separatortheorems gelöst werden.
• "Jede Instanz eines NP-kompletten Problems ist schwierig." Oft sind einige oder sogar die meisten Instanzen leicht in Polynomialzeit zu lösen. Wenn jedoch P=NP ist, muss jeder Polynomialzeit-Algorithmus asymptotisch bei mehr als polynomiell vielen der exponentiell vielen Eingaben einer bestimmten Größe falsch sein.
• "Wenn P=NP ist, können alle kryptographischen Chiffren gebrochen werden." Ein Polynomialzeitproblem kann in der Praxis sehr schwer zu lösen sein, wenn der Grad oder die Konstanten des Polynoms groß genug sind. Beispielsweise können Chiffren mit einer festen Schlüssellänge, wie der Advanced Encryption Standard, alle in konstanter Zeit gebrochen werden, indem jeder Schlüssel ausprobiert wird (und somit ist bereits bekannt, dass sie in P sind), obwohl diese Zeit mit der derzeitigen Technologie das Alter des Universums übersteigen kann. Darüber hinaus bietet die informationstheoretische Sicherheit kryptografische Methoden, die selbst mit unbegrenzter Rechenleistung nicht geknackt werden können. ⓘ

Eigenschaften

Betrachtet man ein Entscheidungsproblem als eine formale Sprache in einer festen Kodierung, so ist die Menge NPC aller NP-vollständigen Probleme nicht geschlossen unter:

• Vereinigung
• Schnittmenge
• Verkettung
• Kleener Stern ⓘ

Es ist nicht bekannt, ob NPC unter Komplementierung geschlossen ist, da NPC=co-NPC nur dann ist, wenn NP=co-NP, und ob NP=co-NP ist eine offene Frage. ⓘ

NP-Äquivalenz

NP-Vollständigkeit ist nur für Entscheidungsprobleme definiert, also für solche Probleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen, für die als Antwort also nur entweder Ja oder Nein in Frage kommt. Für Optimierungsprobleme und Suchprobleme gibt es die Bezeichnung der NP-Äquivalenz. ⓘ

Approximation

Probleme, die in NP liegen, lassen sich weiter in ihrer Komplexität unterteilen, je nachdem, wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem ist beispielsweise nur sehr schlecht approximierbar, während sich andere Probleme beliebig gut mittels so genannter Approximationsschemata approximieren lassen. ⓘ