Was ist NP-Vollständigkeit, gerne auch im Volksmund formuliert.
Zu lösende Probleme in der Informatik teilt man in sogenannte Komplexitätsklassen ein, d.h. im wesentlichen gruppiert man die Probleme nach ihrem Lösungsaufwand in Abhängigkeit von der Eingangsgröße n. Ein Problem kann lösbar sein in:
Analoge Betrachtungen gibt es auch für den Platzbedarf des Algorithmus, der das Problem löst.
Mit P wird nun die Klasse von Problemen bezeichnet, die ein deterministischer Algorithmus in polynomineller Zeit lösen kann, also O(1), O(n) oder O(p). Mit NP wird die Klasse von Problemen bezeichnet, die nur ein nichtdeterministischer Algorithmus in polynomineller Zeit lösen kann. Ein deterministischer Algorithmus braucht dazu mindestens exponentiell viel Zeit, soweit der bisherige Kenntnisstand in der Informatik.
Die Klasse NP umfaßt also "mehr" Probleme als P (ein nichtdeterministischer Algorithmus kann auch ein Problem, das nur zu P gehört, in polynomineller Zeit lösen), deshalb gilt:
P ist Teilmenge von NP
Die große Frage in der Informatik ist nun, ob P eine echte Teilmenge von NP ist. D.h. ob es ein Problem gibt, für das bewiesen werden kann, daß es nur in NP liegt, aber nicht in P. Dann würde nämlich gelten P<>NP. Wenn dagegen P=NP gilt, kann jedes bisher der NP-Klasse zugeordnete Problem auch von einem deterministischen Algorithmus in polynomineller Zeit gelöst werden. Ob man den Algorithmus dabei schon kennt spielt für die Fragestellung keine Rolle.
Die P=NP-Frage ist wesentlich, wenn man entscheiden will, ob man überhaupt hoffen kann, "gute" Algorithmen für NP-Probleme zu finden. Falls P<>NP gilt (d.h. jemand kann das beweisen) hat man leider verloren :-(.
Mit NP-vollständig bezeichnet man nun die Klasse von Problemen für die gilt:
Das bedeutet, daß die Lösung nur eines der als NP-vollständig bekannten Probleme von einem deterministischen Algorithmus in polynomineller Zeit dazu führt, daß alle anderen NP-vollständigen Probleme damit genauso "mitgelöst" würden. Es scheint also so, daß hier ein Grundprinzip gefordert ist, von dem noch niemand weiß ob es überhaupt existiert.
Von Torsten Rupp @ 2:2476/506, 11.12.94
leicht bearbeitet
Erstellt von Ralf Wiebicke, letzte Änderung
26.03.97