NP-vollständige Probleme

Die Mengen P und NP

Im Bereich der Algorithmen entsprechen sich "schwierig" und "zeitaufwändig". Ein Problem ist schwierig, wenn seine Lösung zeitaufwändig ist. Der Begriff zeitaufwändig ist natürlich relativ, aber es hat sich als sinnvoll erwiesen, hier eine Grenze zu ziehen zwischen Problemen mit höchstens polynomieller Zeitkomplexität und Problemen mit größerer als polynomieller Zeitkomplexität.

Definition: Eine Zeitkomplexität von T(n) Element O(n^k) wird als polynomielle Zeitkomplexität bezeichnet. Hierbei ist k ein konstanter Wert, der nicht von n abhängt.

Definition: Ein Problem hat polynomielle Zeitkomplexität, wenn es einen Algorithmus zur Lösung des Problems gibt, der polynomielle Zeitkomplexität hat.

Die Menge aller Entscheidungsprobleme, die polynomielle Komplexität haben, wird mit P bezeichnet.

Beispiel: Sei G = (V, E) ein beliebiger ungerichteter, zusammenhängender Graph mit einer Kantengewichtung w : E natürliche Zahlen sowie m eine beliebige natürliche Zahl.

Das Entscheidungsproblem "Hat G einen Spannbaum mit einem Gewicht m?" liegt in P.

Wir konstruieren einen minimalen Spannbaum, dies erfordert Zeit O(n²), wobei n die Anzahl der Knoten des Graphen ist, und vergleichen das Gewicht des minimalen Spannbaums mit der Zahl m.

Das gedankliche Modell des Nichtdeterminismus haben wir bei den endlichen Automaten kennen gelernt.

Ein nichtdeterministischer endlicher Automat führt eine Berechnung aus, indem er die Zeichen des Eingabewortes w abarbeitet und dabei Zustandsübergänge vollführt. Die Zustandsübergänge sind dabei i.a. nicht eindeutig bestimmt. Daher hat eine Konfiguration, bestehend aus Zustand und noch abzuarbeitenden Eingabezeichen, möglicherweise mehrere Folgekonfigurationen. Dies ist gerade das Kennzeichen des Nichtdeterminismus – es gibt lediglich eine Übergangsrelation und keine Übergangsfunktion.

Bei einem deterministischen endlichen Automaten ist die Folgekonfiguration stets eindeutig bestimmt.

Graphisch dargestellt gleicht die Abfolge der Konfigurationen beim deterministischen endlichen Automaten einer Kette (Bild 1 a) und beim nichtdeterministischen endlichen Automaten einem Baum (Bild 1 b).

Bild 1: Deterministische Berechnung (a), nichtdeterministische Berechnung (b)

Das Konzept des Nichtdeterminismus gibt es auch bei anderen Maschinenmodellen, so bei dem Modell der Turingmaschine oder der Random-Access-Maschine (siehe Kapitel Algorithmen und Komplexität). Hier ist die Situation im Prinzip ähnlich. Da aber etwa die Random-Access-Maschine Werte in den Speicher schreiben kann, ist ihre jeweilige momentane Konfiguration durch ihren Zustand und den gesamten Speicherinhalt bestimmt.

Ein nichtdeterministischer Algorithmus für eine Random-Access-Maschine ist dadurch gekennzeichnet, dass er in jedem Schritt möglicherweise mehrere Wahlmöglichkeiten hat. Eine solche Wahlmöglichkeit könnte beispielsweise darin bestehen, dass der Algorithmus wählen kann, ob er die Anweisung x=1, x=2 oder x=3 ausführt. Je nach dem, welche Möglichkeit er wählt, gerät er in eine andere Folgekonfiguration. Eine Berechnung eines solchen nichtdeterministischen Algorithmus gleicht also ebenfalls einem Baum wie in Bild 1 b dargestellt.

Es ist schwierig, sich einen nichtdeterministischen Algorithmus vorzustellen. Welche Wahl trifft der Algorithmus, wenn er mehrere Wahlmöglichkeiten hat? Hier gibt es mehrere Möglichkeiten der Vorstellung: Eine ist, dass der Algorithmus mit schlafwandlerischer Sicherheit immer die richtige Wahl trifft, die zur Lösung des Problems führt. Die andere ist, dass er alle Wahlmöglichkeiten gleichzeitig durchspielt. Der Algorithmus erzeugt entsprechend viele Kopien von sich selbst, und jede dieser Kopien rechnet in der entsprechenden Folgekonfiguration weiter. Wenn irgendeine dieser Kopien die Lösung des Problems gefunden hat, stoppt der Algorithmus.

Definition: Ein Problem hat nichtdeterministisch polynomielle Zeitkomplexität, wenn es einen nichtdeterministischen Algorithmus zur Lösung des Problems gibt, der polynomielle Zeitkomplexität hat.

Die Menge aller Entscheidungsprobleme, die nichtdeterministisch polynomielle Zeitkomplexität haben, wird mit NP bezeichnet.

Offenbar gilt P enthalten NP, denn wenn es einen deterministischen polynomiellen Algorithmus zur Lösung eines Problems gibt, dann gibt es auch einen nichtdeterministischen polynomiellen Algorithmus zur Lösung des Problems, denn ein deterministischer Algorithmus lässt sich als Spezialfall eines nichtdeterministischen Algorithmus ansehen. Ob allerdings P eine echte Teilmenge von NP ist, weiß man nicht. Dies ist die bekannteste ungelöste Frage der Informatik.

Es sollen nun einige Probleme betrachtet werden, die in NP, aber wahrscheinlich nicht P liegen.

Travelling-Salesman-Problem

Das Travelling-Salesman-Problem (TSP) liegt in NP. Als Entscheidungsproblem formuliert lautet es: "Gegeben n Städte und die Entfernungen zwischen ihnen. Gibt es eine Rundreise der Länge k?" Die Länge einer Rundreise lässt sich deterministisch in linearer Zeit berechnen. Ein nichtdeterministischer Algorithmus verzweigt in jeder Stadt in alle Städte, die er noch nicht besucht hat, und spielt so alle Rundreisen durch.

Erfüllbarkeitsproblem

Definition: Das Erfüllbarkeitsproblem (satisfiability problem – SAT) besteht darin, für eine beliebige boolesche Formel f mit Variablen x₀, ..., x_k-1 die Frage zu beantworten: "Ist f erfüllbar?" Eine boolesche Formel ist erfüllbar, wenn es eine Belegung ihrer Variablen mit den Wahrheitswerten true und false gibt, so dass die Auswertung der Formel den Wahrheitswert true ergibt.

Beispiel: Die Formel

f = (x₀ oder x₁) und (x₀ oder x₁) und (x₀ oder x₁)

ist erfüllbar, denn mit der Belegung x₀ = true und x₁ = false ergibt die Formel den Wert true.

Die Formel

g = x₁ und (x₀ oder x₁) und (x₀ oder x₁)

ist dagegen nicht erfüllbar.

Das Erfüllbarkeitsproblem liegt in NP. Eine boolesche Formel der Länge n lässt sich deterministisch in linearer Zeit auswerten, wenn eine Belegung gegeben ist. Ein nichtdeterministischer Algorithmus verzweigt für jede Variable x_j, auf die er bei der Auswertung trifft, in die beiden Möglichkeiten x_j = true und x_j = false und spielt dadurch alle Belegungen durch.

Cliquen-Problem

Definition: Das Cliquen-Problem (CLIQUE) besteht darin, für einen beliebigen ungerichteten Graphen G mit n Knoten und für beliebiges k Element natürliche Zahlen die Frage zu beantworten: "Enthält G eine k-Clique?" Eine k-Clique ist ein vollständig verbundener Teilgraph mit k Knoten.

Das Cliquen-Problem liegt in NP. Der nichtdeterministische Algorithmus verzweigt im ersten Schritt zu allen Knoten des Graphen. Von diesen Knoten aus verzweigt er zu allen benachbarten Knoten, von dort aus wiederum zu den benachbarten Knoten usw., insgesamt k-mal. In jedem Schritt prüft der Algorithmus (in polynomieller Zeit), ob der neue Knoten von allen bisher besuchten verschieden ist und mit diesen allen verbunden ist. Ist dies in allen k Schritten der Fall, so hat er eine k-Clique gefunden.

Hamiltonscher Kreis

Definition: Gegeben ist ein ungerichteter Graph G = (V, E). Ein Hamiltonscher Kreis ist ein Kreis, der alle Knoten enthält, also ein Pfad, der jeden Knoten genau einmal durchläuft und zum Ausgangsknoten zurückführt.

Das Problem des Hamiltonschen Kreises (Hamiltonian circuit – HC) besteht darin, für einen beliebigen ungerichteten Graphen G zu entscheiden, ob G einen Hamiltonschen Kreis enthält.

Das Problem des Hamiltonschen Kreises liegt in NP. Ein nichtdeterministischer Algorithmus zur Lösung von HC verzweigt an jedem Knoten zu allen benachbarten Knoten, die er noch nicht besucht hat, und sucht so alle Pfade durch den Graphen, die alle Knoten genau einmal enthalten und zum Ausgangsknoten zurückführen.

Weiter mit: [NP-Vollständigkeit] oder

NP-vollständige Probleme

Die Mengen P und NP

Die Menge P

Nichtdeterministische Algorithmen