Vollständig heißt diese Problemklasse deshalb, weil alle Probleme dieser Klasse irgendwie miteinander in Verbindung stehen. Wenn es gelänge, eines dieser NP-vollständigen Probleme zu lösen, könnte man alle anderen auch lösen.
Wie sieht diese Verbindung aus?
Man kann jedes Problem dieser Klasse in ein anderes umwandeln.
Wenn P, Q Elemente aus NPC sind, dann folgt daraus:
Sehen wir uns als Beispiel die Umwandlung des Hamiltonschen Pfades ins TSP an:
Gegeben sei ein Graph G (Hamiltonscher Pfad) mit n Knoten. Konstruiere den Graphen T (TSP) auf die folgende Art und Weise:Wenn G einen Hamiltonschen Pfad besitzt, dann kann man die maximale Größe der optimalen Tour von T genau angeben.
Sei n die Anzahl der Knoten. Wie groß ist maximal die optimale Tour aus T?
|
|
|
|
|---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996