Von leichten, schweren und vollständigen Problemen

Vor ein paar Wochen habe ich euch das Konzept der Berechenbarkeit in der Informatik vorgestellt. Damit lässt sich die Frage beantworten, ob ein Problem berechenbar ist oder nicht. Wenn irgendwo (zum Beispiel in der Biologie) eine neue Fragestellung auftaucht, muss diese zuerst als informatisches Problem formuliert werden. Dann wird das Problem auf Berechenbarkeit überprüft. Ein Problem ist berechenbar, wenn man dafür einen Algorithmus schreiben kann. Damit ist das Problem theoretisch mit einem Computer lösbar. Aber wie die österreichische Schriftstellerin Marie von Ebner-Eschenbach schon sagte: „Theorie und Praxis sind eins wie Leib und Seele, und wie Seele und Leib liegen sie großenteils miteinander in Streit.” Werfen wir also einen Blick auf die praktische Lösbarkeit von Problemen.

Allerdings brauchen wir auch hierfür wieder ein wenig Theorie. Das Teilgebiet der (theoretischen) Informatik, das sich mit der Schwere von Problemen beschäftigt, heißt Komplexitätstheorie. In diesem Forschungsgebiet werden Probleme in Komplexitätsklassen eingeordnet. Jedes (neue) berechenbare Problem wird in eine Schublade sortiert, je nach dem wie schwierig es ist. Diese Klassifizierung funktioniert leider nicht automatisch wie beim Machine Learning, sondern durch Beweise.

Dabei ist die wichtigste Frage: Wie viel Zeit braucht ein Rechner, um ein Problem zu lösen? Die Zeit messen wir nicht in Sekunden oder Minuten, sondern als Anzahl der maximal notwendigen Rechenschritte, die wir benötigen, um das Problem zu lösen. Und das in Abhängigkeit von der Größe der Eingabe. Willst du die Summe aus zehn Zahlen berechnen brauchst du ja auch länger, als für die Summe aus zwei Zahlen. Die Schwierigkeit des Problems ist unabhängig von dem Computer, auf dem es gelöst werden soll. Die als „schwer“ bezeichneten Probleme sind auch für die jeweils nachkommende, schnellere Rechnergeneration noch schwer.

Die Klasse NP besteht aus drei Schubladen: wir nennen sie P, NP und NPC.

Die zwei bekanntesten Schubladen sind wohl P und NP. Genau genommen ist P eine Schublade innerhalb der Klasse NP. Die Klasse NP besteht eigentlich aus drei Schubladen: wir nennen sie P, NP und NPC. Was hat es mit diesen Schubladen auf sich?

Die Schublade P

In dieser Schublade liegen alle Probleme, die man in Polynomialzeit (=P) lösen kann. Polynomialzeit bedeutet n^k, wobei n die Größe der Eingabe ist und k eine feste Konstante. Polynomialzeit ist also zum Beispiel lineare Zeit: um fünf Zahlen zu addieren brauchen wir fünf Rechenschritte — die Laufzeit ist also gleich der Eingabegröße. Auch wenn sie dreimal oder hundert mal so groß wäre, ist das noch immer lineare Zeit. Auch quadratische oder kubische Zeit ist polynomiell.

Formal definiert sind in der Schublade P alle Probleme, für die eine deterministische Turingmaschine existiert, die das Problem in Polynomialzeit löst. Deterministisch bedeutet, dass bei gleicher Eingabe immer genau die gleichen Rechenschritte (Zustände der Turingmaschine) ablaufen und immer genau das gleiche Ergebnis raus kommt. Zu jedem Zeitpunkt ist der nächste Schritt des Algorithmus eindeutig festgelegt.

Alle Probleme, die in der Schublade P liegen, sind für Informatiker einfach zu lösende Probleme. Und damit für die theoretischen Informatiker eher langweilig…

Die drei Schubladen der Klasse NP

Die Klasse NP besteht aus drei Schubladen: wir nennen sie P, NP und NPC. NP steht für “nichtdeterministische Polynomialzeit”. Zu dieser Klasse gehören alle Probleme, die man mit einer nichtdeterministischen Turingmaschine in Polynomialzeit lösen kann. Nichtdeterministisch bedeutet, dass die Maschine zu jedem Zeitpunkt potentiell mehrere Möglichkeiten hat, ihre Berechnung fortzusetzen. Anders als bei einer deterministischen Turingmaschine gibt es also keinen eindeutigen Rechenweg. Alle Probleme, die man mit einer deterministischen Turingmaschine lösen kann, lassen sich aber auch von einer nichtdeterministischen Turingmaschine lösen. Die Schublade P gehört also zur Klasse NP.

Nichtdeterministische Turingmaschinen sind nur ein theoretisches Modell. Unsere Computer funktionieren leider nicht auf diese Weise. Die Frage ist: kann man diese Probleme auch mit unseren (deterministischen) Computern in Polynomialzeit lösen? Zumindest kann man sie in Polynomialzeit verifizieren. Soll heißen: der Rechner kann für eine vorgeschlagene Lösung in Polynomialzeit entscheiden, ob sie stimmt. Ihr könnt euch das ähnlich vorstellen, wie bei einem Rätsel. Häufig ist es schwierig, auf die Lösung des Rätsels zu kommen. Wenn euch aber jemand die Lösung verrät, könnt ihr sie vermutlich ganz schnell nachvollziehen.

Bevor wir uns die beiden anderen Schubladen der Klasse NP angucken, brauchen wir noch eine andere Klasse, sie nennt sich NP-schwer. Aha “schwer” — denkt ihr euch vermutlich. Endlich geht’s zur Sache. Ein Problem (nennen wir es donald) ist NP-schwer, wenn es mindestens so schwer wie jedes andere Problem in NP ist. Alle Probleme, die in der Klasse NP liegen, müssen sich in polynomieller Zeit auf das Problem donald zurückführen lassen. Das heißt, man kann alle Probleme in NP in polynomieller Zeit so umformulieren, dass die Lösung des Problems donald auch all die anderen Probleme löst.

Die Schublade NPC

Vergleich von linearer, kubischer und exponentieller Laufzeit.

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 kⁿ, 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.

Hamilton vs. Euler

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.

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.

Was liegt eigentlich in der NP-Schublade?

Vielleicht ist euch aufgefallen, dass ich bisher von keinem Problem gesprochen habe, das in der NP-Schublade liegt. Ist diese Schublade leer? Bisher schon. Denn wir kennen (noch?) keine Probleme, die in dieser Schublade liegen. Bis auf eine Ausnahme: Ein künstliches Problem ohne praktische Relevanz. Wozu? Dieses Problem hat sich 1975 Richard Ladner ausgedacht, um eben diese Frage zu beantworten, ob die NP-Schublade leer ist. Er hat also ein Problem entworfen, das weder in die P, noch in die NPC Schublade gehört, aber eben trotzdem zur Klasse NP. Natürlich nur, wenn P≠NP (sonst schütten wir ja eh alle drei Schubladen zusammen). Es gibt aber auch in der Praxis ein paar Probleme, von denen man vermutet, dass sie in dieser Schublade liegen. Zum Beispiel die Primfaktorzerlegung: die Darstellung einer natürlichen Zahl als Produkt aus Primzahlen. Interessant ist das vor allem für Verschlüsselungsverfahren in der Kryptographie.

Wie lösen wir denn nun die schweren Probleme?

Natürlich nützt es nix zu sagen “Joa, das Problem ist schwer, da können wir jetzt leider nix machen”. So denkt ein Informatiker nicht. Stattdessen müssen wir uns eben ein Paar Tricks und Kniffe einfallen lassen — aber von denen berichte ich euch ein anderes Mal.

Beitrag auf ScienceBlogs.de lesen.