Vergleich von linearer, kubischer und exponentieller Laufzeit.
Die Schublade NPC
Zurück zu unseren Schubladen. Die Schublade NPC steht für NP-vollständig (engl.: NP-complete). In diese Schublade wandert ein Problem, wenn es sowohl zur Klasse NP gehört (also mit einer nichtdeterministischen Turingmaschine in Polynomialzeit lösbar ist), als auch NP-schwer ist. Für die Probleme in dieser Schublade, hat bis heute noch niemand einen Polynomialzeitalgorithmus für unsere (deterministischen) Rechner gefunden. Bisher sind zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen bekannt. Exponentialzeit bedeutet kn, das heißt, die Größe der Eingabe wirkt sich exponentiell auf die Laufzeit aus. Und das wiederum bedeutet, dass die echte Laufzeit ganz schnell auf Milliarden von Jahren anwächst. Da nützt es uns auch nix, wenn wir auf die nächste (doppelt so schnelle) Rechnergeneration warten, um das Problem zu lösen.
Ein Eulerkreis läuft durch jede Kante genau einmal (darf aber einen Knoten mehrmals passieren). Ein Hamiltonkreis verläuft durch jeden Knoten genau einmal (muss aber nicht jede Kante passieren). Für das “Haus vom Nikolaus” (oben) gibt es einen Euler- und einen Hamiltonkreis. Für den unteren Graph gibt es keinen Hamiltonkreis.
Hamilton vs. Euler
Manchmal ähneln sich Probleme auf den ersten Blick sehr, wandern dann aber doch in zwei unterschiedliche Schubladen. So zum Beispiel bei der Suche nach dem Eulerkreis und dem Hamiltonkreis. Ein Graph ist in der Informatik ein Gebilde aus Knoten und Kanten. Das Haus vom Nikolaus zum Beispiel ist ein Graph, wobei jede Ecke ein Knoten ist. Ein Eulerkreis läuft durch jede Kante genau einmal (darf aber einen Knoten mehrmals passieren). Ein Hamiltonkreis verläuft durch jeden Knoten genau einmal (muss aber nicht jede Kante passieren). Klingt erstmal sehr ähnlich. Zu erkennen ob es einen solchen Kreis gibt, ist aber für das eine Problem einfach, für das andere nicht. Einen Eulerkreis gibt es genau dann, wenn der Graph zusammenhängend ist und jeder Knoten eine gerade Anzahl an Kanten besitzt. Das Eulerkreisproblem liegt in der Schublade P. Für den Hamiltonkreis gibt es solch eine einfache Überprüfung nicht, es liegt in der Schublade NPC.
P vs. NP ?
Für die Probleme in NPC hat also noch keiner einen Polynomialzeitalgorithmus gefunden. ABER: es konnte auch noch keiner beweisen, dass es kein Polynomialzeitalgorithmus dafür geben kann. Brauchen wir wirklich die drei einzelnen Schubladen P, NP und NPC? Oder ist P = NP und wir können alles in eine Schublade schmeißen? Oder anders gefragt: wenn man ganz leicht überprüfen kann, ob eine Lösung richtig ist, kann man die Lösung dann auch einfach finden? Bekannt ist diese Fragestellung schon seit den 70ern und sie ist eine der wichtigsten Fragestellungen der Informatik. So wichtig, dass sie in der Liste der Millennium-Probleme steht, für deren Lösung man mal eben eine Million US-Dollar abstauben kann.
Die Frage könnte man auch anders formulieren: Sind wir einfach nur zu dumm, bessere Algorithmen zu finden? Würden wir nur für ein einziges der Probleme in NPC einen Polynomialzeitalgorithmus finden, könnte wir jedes Problem aus der Klasse NP in Polynomialzeit lösen (denn wir haben ja gelernt, dass sich alle Probleme, die in der Klasse NP liegen, in polynomieller Zeit auf donald zurückführen lassen). Die NPC-Schublade ist mittlerweile aber schon ziemlich voll. Und nicht für eines dieser Probleme ist es gelungen, einen solchen Algorithmus zu entwerfen. Und da der Mensch im allgemeinen und der Informatiker im speziellen sich nicht gerne für dumm hält, vermutet der Großteil der Fachwelt, dass P≠NP gilt.
Es gab und gibt natürlich schon einige Versuche, P=NP oder P≠NP zu beweisen. Allein 2016 vier für P≠NP und einen für P=NP. Hier gibt es eine Liste der verschiedenen Beweisführungen. Keine davon ist jedoch bestätigt und die eine Millionen US-Dollar stehen immer noch zum Abstauben bereit.
Kommentare (2)