#NP-Vollständigkeit des SAT-Problems – Mathlog

Das Erfüllbarkeitsproblem der Aussagenlogik – auch als SAT-Problem bezeichnet nach dem englischen Begriff satisfiablity für Erfüllbarkeit – fragt nach der Erfüllbarkeit einer gegebenen aussagenlogischen Formel durch eine geeignete Variablenbelegung. Man kann das Problem natürlich durch Aufstellen einer Wahrheitstabelle lösen, aber dann wächst der Zeitverbrauch exponentiell mit der Anzahl der Variablen. Man weiß bis heute nicht, ob es einen Algorithmus gibt, der das Problem in polynomieller Zeit löst.

Bei einem Symposium der Association for Computing Machinery präsentierte Stephen Cook 1971 eine Arbeit „The complexity of theorem proving procedures“. In dieser Arbeit ging es darum, dass für viele Probleme, deren Lösung man nicht in polynomieller Zeit findet, es aber jedenfalls möglich ist, die Korrektheit einer gefundenen Lösung in polynomieller Zeit zu überprüfen. In der ein Jahr später von Karp eingeführten Terminologie nennt man die Klasse dieser Probleme NP, während P die Klasse der in polynomieller Zeit lösbaren Probleme bezeichnet. Beispielsweise gehört das SAT-Problem zu NP, denn man kann leicht überprüfen, ob eine gegebene Variablenbelegung eine aussagenlogische Formel erfüllt.

Cook bewies überraschend, dass sich jedes Problem, dessen Lösungen in polynomieller Zeit überprüft werden können, auf das SAT-Problem reduzieren läßt, also dass es zu jedem solchen Problem A einen Algorithmus in polynomieller Zeit zur Lösung von A mit Zugang zu einem Orakel für das SAT-Problem gibt. 

Ebenso bewies er, dass sich jedes solche Probleme auch auf das Teilgraphenisomorphismusproblem reduzieren läßt. In diesem Problem geht es darum, für zwei gegebene Graphen G und H zu entscheiden, ob es einen Teilgraphen von G isomorph zu H gibt. In seinem Konferenzbeitrag schrieb er, dass es damit wohl fruchtlos wäre, nach einer Lösung des Teilgraphenproblems in polynomieller Zeit zu suchen, denn das würde polynomielle Algorithmen für viele andere unzugängliche Probleme liefern.

Diese Arbeit wurde zunächst nur von Logikern beachtet. Ein Jahr später erstellte Richard Karp dann aber eine Liste von 21 Problemen, auf die sich jedes Problem aus NP reduzieren läßt. Die meisten der Probleme waren aus der Graphentheorie, bei einigen handelte es sich um in der Realwelt vorkommende Optimierungsprobleme. Karp nannte solche Probleme NP-schwer. Probleme, die sowohl in NP als NP-schwer sind, nannte er NP-vollständig. Seine Liste war also eine Liste von 21 NP-vollständigen Problemen. Weiter erwähnte er einige der Konsequenzen, wenn P=NP wäre. Dieses Problem und die Suche nach NP-vollständigen Problemen wurden in der Folge zur sehr populären Themen der theoretischen Informatik.

Karp bewies beispielsweise, dass sich das Erfüllbarkeitsproblem der Aussagenlogik auf das Cliquenproblem reduzieren läßt. Dieses fragt, ob es zu einem gegebenen Graphen G und einer Zahl n eine Clique (d.h. einen vollständigen Graphen) der Größe n in G gibt. Dieses Problem ist also ebenfalls NP-vollständig.
Das Cliquenproblem wiederum konnte er auf das Knotenüberdeckungsproblem zurückführen: gegeben einen Graphen G und eine Zahl k, gibt es eine Menge von k Knoten, so dass jede Kante mit mindestens einem der k Knoten verbunden ist?
Das Knotenüberdeckungsproblem wiederum führte er zurück auf das Problem, ob es in einem Graphen einen Hamilton-Kreis (einen jeden Knoten genau einmal durchlaufenden Kreis) gibt. Damit sind auch diese beiden Probleme NP-vollständig.
Ein anderes von ihm als NP-vollständig bewiesenes Problem war das 3-SAT-Problem: ist eine in konjunktiver Normalform vorliegende aussagenlogische Formel, die höchstens 3 Literale pro Klausel enthält, erfüllbar? Dieses wiederum läßt sich auf das Graphfärbungsproblem zurückführen und das dann auf das Rucksackproblem, ein klassisches Optimierungsproblem: aus einer Menge von Objekten mit Gewicht und Nutzwert soll unter den ein vorgegebenes Gesamtgewicht nicht überschreitenden Teilmengen die den Nutzwert maximierende gefunden werden. Und dieses Optimierungsproblem läßt sich auf die Konstruktion eines maximalen Schnittes in einem Graphen zurückführen, d.h. die Zerlegung der Knotenmenge eines Graphen, so dass man eine maximale Zahl zwischen den Teilen verlaufender Kanten hat.
Tatsächlich ließ sich mit Ausnahme der 0-1-ganzzahligen Optimierung die NP-Vollständigkeit aller Probleme in seiner Liste auf die NP-Vollständigkeit entweder des Cliquenproblems oder des 3-SAT-Problems zurückführen und diese beiden ebenso wie die 0-1-ganzzahlige Optimierung sich dann schlußendlich auf das Erfüllbarkeitsproblem der Aussagenlogik.