NP-vollständige Probleme

Die Mengen P und NP

 aufwärts

Im Bereich der Algorithmen entsprechen sich "schwierig" und "zeitaufwendig". Ein Problem ist schwierig, wenn seine Lösung zeitaufwendig ist. Der Begriff zeitaufwendig 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.

Die Menge P

Definition:  Eine Zeitkomplexität von T(nElement O(nk) 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 Pfeil nach rechts natürliche Zahlen sowie k eine beliebige Zahl.

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

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

Nichtdeterministische Algorithmen

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

Ein nichtdeterministischer Algorithmus 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 frei wählen kann, ob er die Anweisung x=1, x=2 oder x=3 ausführt. Wohlgemerkt, er trifft seine Wahl nicht deterministisch etwa aufgrund einer Bedingung (wie bei einer If-Anweisung in einem deterministischen Algorithmus), sondern nichtdeterministisch. Je nach dem, welche Möglichkeit er wählt, gerät er aus seiner aktuellen Konfiguration in eine andere Folgekonfiguration. Eine solche Wahlmöglichkeit gibt es bei einem deterministischen Algorithmus nicht, die jeweilige Folgekonfiguration ist stets eindeutig bestimmt. Auch bei einer Verzweigung aufgrund einer Bedingung ist die Folgekonfiguration eindeutig, je nach dem, ob die Bedingung wahr oder falsch ist. Eine Berechnung eines deterministischen Algorithmus lässt sich durch eine Kette von Konfigurationen wie in Bild 1a veranschaulichen. Eine Berechnung eines nichtdeterministischen Algorithmus gleicht dagegen einem Baum von Konfigurationen wie in Bild 1b.

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

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.

Die Menge NP

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 in 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 kleiner gleichk?" 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 problemSAT) besteht darin, für eine beliebige boolesche Formel f mit Variablen x0, ..., xk-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, sodass die Auswertung der Formel den Wahrheitswert true ergibt.

Beispiel:  Die Formel

f  =  (x0  oder  x1)  und  (x0  oder  x1)  und  (x0  oder  x1)

ist erfüllbar, denn mit der Belegung x0 = true und x1 = false ergibt die Formel den Wert true.

Die Formel

g  =  x1  und  (x0  oder  x1)  und  (x0  oder  x1)

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 xj, auf die er bei der Auswertung trifft, in die beiden Möglichkeiten xj = true und xj = 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 circuitHC) 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 up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 25.05.2006   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik