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 nk, 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.
Kommentare (2)