The P versus NP Problem


Das Problem P vs NP ist ein Problem aus der Komplexitätstheorie. In der Komplexitätstheorie untersucht man die Probleme, die von einem Computer gelöst werden können und unterteilt sie je nach ihrer Schwierigkeit in mehrere Kategorien. Damit ein Problem von einem Computer gelöst werden kann muss zumindest theoretisch ein Ergebnis berechenbar sein—selbst wenn man Millionen von Jahren auf das Ergebnis warten müsste. Darum sind Problemstellungen wie beispielsweise “Bin ich schön?” oder “Wie lauten die Lotto-Zahlen von nächster Woche?” keine Probleme, die von einem Computer gelöst werden können. Solche Probleme werden in der Komplexitätstheorie deshalb auch nicht untersucht. Entscheidend ist hierbei allerdings die Formulierung des Problems. Antworten auf Fragen wie “Ist dieser Mensch schön?” sind extrem subjektiv; die eine Person sagt “ja”, die nächste sagt “nein”. Für einen Computer ist dieses Problem also unentscheidbar. Das umformulierte Problem “Stimmt die überwiegende Mehrheit einer Gruppe von befragten Menschen zu, dass die gezeigte Person schön ist?” lässt sich hingegen sehr wohl von einem Computer entscheiden (indem man einfach eine Gruppe von Menschen befragt, das Ergebnis auswertet und mit dem vorher definierten Grenzwert vergleicht).

Sehr viele Aufgaben können von einen Computer ziemlich leicht gelöst werden. Beispiele wären “Prüfe ob eine Zahl durch 3 teilbar ist”, “Bilde das Quadrat einer Zahl” oder “Sortiere eine Liste von Wörtern alphabetisch”. In der Komplexitätstheorie klassifiziert man aber lediglich Entscheidungsprobleme, d.h. wir müssen unsere Beispielprobleme noch entsprechend umformulieren zu “Ist Zahl X durch 3 teilbar, ja oder nein?”, “Ist Zahl Y das Quadrat von Zahl X, ja oder nein?” und “Entspricht Liste B der sortierten Liste A, ja oder nein?”. Da die ursprünglichen Formulierungen der Problems effizient lösbar sind für alle Zahlen bzw. Listen von Wörtern, können auch deren Entscheidungsproblem-Varianten mit geringem bis akzeptablem Aufwand nachgeprüft werden (das Wort alle ist extrem wichtig, mehr dazu später). Man kann die Entscheidungsprobleme lösen, indem man beispielsweise einfach das Quadrat von X bildet und es mit Y vergleicht bzw. eine Liste A sortiert und mit Liste B vergleicht. Ist ein Problem einfach lösbar, so nennt man das in der Komplexitätstheorie “in Polynomialzeit lösbar”, also in absehbarer Zeit. Die Kategorie der einfach lösbaren Probleme nennt man die Komplexitätsklasse P (P wegen Polynomial).

Die Kategorie der einfachen Probleme hätten wir damit abgehakt. Was ist mit den übrigen Problemen? Sind das automatisch die schweren Probleme? Vergiss nicht, wie wir einfache Probleme definiert haben. Ein Problem ist genau dann einfach, wenn es für alle möglichen Eingabewerte effizient lösbar ist. Das bedeutet also nicht, dass ein Problem schwierig sein muss, nur weil es (noch) nicht in der Kategorie der einfachen Probleme ist. Es bedeutet lediglich, dass wir noch nicht herausgefunden haben, wie wir das Problem für alle möglichen Eingabewerte effizient lösen können. Aber vielleicht finden wir das ja eines Tages noch heraus. Selbstverständlich könnte das Problem tatsächlich extrem schwierig sein und wir werden niemals auf die Lösung kommen. Es kann aber auch sein, dass bisher einfach noch niemand auf die richtige Idee gekommen ist.

Betrachte beispielsweise das Problem der Primfaktorzerlegung. Zwar ist das Problem für sehr viele Eingabewerte extrem einfach. Beispielsweise können wir die Zahl 30 zerlegen in 2∗3∗5. Genauso können wir die Zahl 6936 zerlegen in 2∗2∗2∗3∗17∗17. Aber wie sieht es mit unvorstellbar großen Zahlen aus? Zahlen, die so viele Stellen haben, dass sie ein ganzes DIN-A4 Blatt füllen? Daran zeigt sich, dass wir das Problem der Primfaktorzerlegung eben nicht für alle möglichen Zahlen effizient lösen können, sofern die Zahl nur genügend groß sind. Aber vielleicht ändert sich das ja noch eines Tages, sobald Quantencomputer Marktreife erreichen.

Das Entscheidungsproblem “Ist 2∗2∗3∗5∗13∗17 die Primfaktorzerlegung von 13260, ja oder nein?” hingegen kann man natürlich extrem leicht überprüfen, indem man einfach 2∗2∗3∗5∗13∗17 berechnet und prüft, ob dabei 13260 heraus kommt. Genauso verhält es sich mit allen anderen Zahlen. Egal wie groß eine Zahl ist, wenn ich dir dazu eine Primfaktorzerlegung nenne (unabhängig davon, ob sie korrekt oder falsch ist) kannst du ganz einfach bestätigen oder widerlegen, ob es sich um die zugehörige Primfaktorzerlegung handelt. Die Primfaktorzerlegung lässt sich zwar nicht effizient für alle möglichen Zahlen lösen, sie lässt sich aber sehr wohl effizient für alle Zahlen überprüfen. Solche Probleme, deren Lösung sich effizient überprüfen lässt, stecken wir in die Komplexitätsklasse NP. Die Klasse P liegt offensichtlich innerhalb der Klasse NP, denn wenn wir ein Problem effizient lösen können, dann können wir auch effizient eine mögliche Lösung überprüfen. Ein anderes Beispiel für ein Problem, welches zwar innerhalb von NP liegt, aber nicht erwiesenermaßen in P, ist das mit heutigen Mitteln unlösbare Faktorisierungsproblem—der Grundlage unserer heutigen RSA-Verschlüsselung. Zwei zufällige Primzahlen miteinander zu multiplizieren ist simpel. Die Gegenrichtung hingegen—das Ergebnis ohne Kenntnis der beiden Primzahlen zu faktorisieren, sodass genau diese beiden Primzahlen herauskommen—ist für genügend große Zahlen extrem schwierig, sprich unmöglich. Wäre das Faktorisierungsproblem in der Klasse P, so würde eine Möglichkeit existieren die gesamte heutige Verschlüsselung zu brechen. Sie müsste zwar noch gefunden werden, aber man wüsste immerhin sicher, dass es sie gibt.

Die Klassen P und NP darf man sich nicht wie Schubladen vorstellen, welche häufig zur Erklärung herangenommen werden. Denn Schubladen implizieren, dass ein Problem nur genau einer Kategorie zugehörig sein können. Die Probleme aus P liegen aber sowohl in P als auch in NP. Sofern man die Schubladen nicht ineinander stapelt, fliegt einem also allein hier schonmal der bildliche Vergleich mit einer Kommode um die Ohren. Außerdem wechseln Probleme nicht ihren Standort bzw. ihre Schublade. Sollte man irgendwann einmal den Beweis finden, dass sich die Primfaktorzerlegung für alle möglichen Zahlen effizient lösen lässt, dann wandert das Problem nicht plötzlich aus der Schublade NP in die Schublade P. Das schwere Problem ist nicht in der Sekunde, in der man den Beweis entdeckt hat, plötzlich einfach geworden. In dem Fall wäre es schon immer einfach gewesen, es war bloß noch niemandem bewusst. Wenn überhaupt müsste man sich die Probleme vorstellen wie Umzugskisten auf dem Dachboden. Die Kisten stehen kreuz und quer durcheinander, sie stehen nicht zwangsweise in Gruppen zusammen. Entdeckt man nun, dass ein Problem aus NP ebenfalls in P liegt, dann bekommt die Umzugskiste höchstens einen P-Aufkleber aufgeklebt zusätzlich zum NP-Aufkleber. Aber die Kiste bleibt stehen wo sie ist und wandert nicht plötzlich in die Ecke zu den anderen Problemen aus P. Denn nicht das Problem hat sich geändert, lediglich unsere Betrachtungsweise darauf.

Ein solches Problem, für das erst sehr spät erkannt wurde, dass es nicht nur in NP, sondern sogar in P liegt, ist das Problem PRIMES. Dabei handelt es sich um den Primzahltest, also das Entscheidungsproblem “Ist Zahl X eine Primzahl, ja oder nein?”. Für kleine Zahlen mag man das noch im Kopf hinbekommen, bis zu einer gewissen Grenze bekam das ein Computer auch noch hin; für Zahlen größer dieser Grenze konnte mit den damaligen Kenntnissen selbst ein Computer das Problem aber nicht mehr effizient lösen. Das Problem konnte also nicht für alle möglichen Eingabewerte gelöst werden und lag somit nicht in P. Im Jahr 2002 wurde aber eine neue Methode entdeckt, mittels der ein Computer nun in der Lage ist für jede beliebige und noch so große Zahl mit akzeptablem Aufwand die Frage nach der Primalität korrekt mit “ja” oder “nein” zu beantworten. Das Problem PRIMES ist seitdem effizient für alle Zahlen lösbar und gehört nun ebenfalls zur Klasse P.

Neben den Klassen P und NP gibt es noch die Klasse NP-Schwere. Ein Problem gehört zu der Klasse NP-Schwere, falls eine Lösung des NP-schweren Problem ebenfalls jedes Problem in NP lösen würde. Man muss also jedes Problem in NP, auch die heute noch nicht effizient lösbaren Probleme, auf irgendeine Weise dermaßen umformulieren können, sodass man das Problem statt mit seiner eigenen Lösung auch mit der Lösung des NP-schweren Problems lösen könnte. Diese Umformulierung nennt man Polynomialzeitreduktion. Zum besseren Verständnis kann man sich bewusst machen, dass man beispielsweise das Quadrieren einer Zahl auch mit dem Algorithmus zur Multiplikation zweier Zahlen lösen kann, in dem Fall eben einer Zahl mit sich selbst. Würde man eine Lösung für ein NP-schweres Problem finden, so hätte man also zusätzlich auf einen Schlag sämtliche Probleme in NP gelöst. Befindet sich das NP-schwere Problem selbst ebenfalls in NP, so ist es nicht nur NP-schwer, sondern auch noch NP-vollständig. Ein NP-schweres Problem muss sich allerdings nicht in der Klasse NP befinden. Wie wir wissen, müssen sich mögliche Lösungen zu einem Problem effizient überprüfen lassen, damit das Problem in NP liegt. Es gibt allerdings auch Probleme, deren Lösung ich nicht einmal dann nachvollziehen kann, selbst wenn mir die korrekte Lösung gesagt wird. Ein Beispiel hierfür ist das Halteproblem. Das Halteproblem beschreibt die Frage, ob ein Algorithmus bis zum Ende abgearbeitet wird und seine Ausführung z.B. mit der Ausgabe des korrekten Ergebnisses beendet. Um lösbar zu sein (man spricht auch von entscheidbar) müsste das Halteprogramm wieder für alle möglichen Eingabewerte (in diesem Fall für alle Algorithmen) lösbar sein. Dies ist aber nicht möglich, sofern nicht noch die Zeitmaschine erfunden wird oder wir lernen in die Zukunft zu sehen. Denn direkt nachdem ich sage “Ja, dieser Algorithmus wird zum Ende kommen.” könnte der Algorithmus in eine Endlosschleife geraten und würde doch nicht zum Ende kommen. Damit hätte ich die falsche Antwort gegeben und das Halteproblem ist nicht mehr für alle Eingabe-Algorithmen effizient und korrekt lösbar. Andererseits könnte mir auch jemand sagen, ein laufender Algorithmus wird niemals zum Ende kommen. Nach Stunden des Wartens beende ich das Programm. Selbst wenn der Algorithmus wirklich nie zum Ende gekommen wäre und die Lösung damit korrekt gewesen wäre, kann ich das nicht überprüfen, denn es hätte ja sein können, dass sich das Programm noch gefangen hätte und doch noch zum Ende gekommen wäre, hätte ich es nicht vorzeitig beendet.

Das Problem P vs NP beschäftigt sich nun mit der Frage, ob P eine echte Teilmenge von NP ist oder ob die Kategorien P und NP eventuell identisch sind. Anders ausgedrückt: lässt sich jedes Problem, dessen mögliche Lösungen in absehbarer Zeit überprüfbar sind, auch in Polynomialzeit für alle möglichen Eingaben lösen? Oder müssen wir einfach akzeptieren, dass es gewisse Probleme gibt, welche wir niemals effizient für alle möglichen Eingaben werden lösen können? Im ersten Fall wäre es ohne jeden Zweifel möglich, dass das Faktorisierungsproblem für alle Zahlen lösbar ist. Damit wäre es nur eine Frage der Zeit, bis unsere sämtliche Verschlüsselung geknackt werden kann (oder eventuell bereits von Geheimdiensten geknackt wurde?). Im zweiten Fall könnte hingegen noch die Chance bestehen, dass das Faktorisierungsproblem für genügend große Zahlen niemals gelöst werden kann und unsere heutige Verschlüsselung damit für immer sicher wäre.

Aber wäre wirklich P=NP und wären sämtliche heute ungelösten Probleme in Wirklichkeit alle einfach, dann wäre es doch wahrscheinlich, dass irgendwann im Laufe der gesamten Menschheitsgeschichte von allen Menschen dieser Erde irgendjemand doch schon einmal zumindest für ein einziges der vielen angeblich einfachen Probleme—hier einige Beispiele—einen Lösungsansatz gefunden hätte.

Würde der Fall P=NP gelten, so wären alle nach unserer heutigen Auffassung schweren Probleme in Wirklichkeit gar nicht schwierig. Mit sämtlichen entscheidbaren Probleme würde eines Tages genau das Selbe passieren wie mit PRIMES. Für Probleme, an denen Computer heutzutage noch Millionen von Jahren rechnen müssten, wie z.B. die Primfaktorzerlegung oder das Traveling Salesman Problem, würde jemand eines Tages einen brillianten neuen Lösungsansatz entdecken können, der das Problem mit einem Schlag effizient lösen kann. Es gäbe also für sämliche bislang ungelösten entscheidbare Computer-Problem eine Lösung, die nur darauf wartet entdeckt zu werden. Das würde gleichzeitig aber ebenfalls bedeuten, dass alle NP-vollständigen Probleme außerdem in P liegen. Und das würde wiederum bedeuten, dass sich jedes Problem in NP so umformulieren ließe, dass es sich von einem beliebigen, bereits heute effizient arbeitenden Algorithmus lösen lassen ließe. Es ließe sich also jedes beliebige Problem von jedem beliebigen Algorithmus lösen, nachdem man das Problem entsprechend umformuliert hat. Man könnte somit das Problem “Ist Zahl X eine Primzahl?” mit dem selben Algorithmus lösen, der Listen alphabetisch sortiert. Man könnte sogar die gesamte heutige Verschlüsselung knacken mit dem Algorithmus, der Listen alphabetisch sortiert. Man könnte ebenfalls die gesamte heutige Verschlüsselung knacken mit dem Algorithmus, der einfach nur zwei Zahlen miteinander multipliziert. Man müsste vorher lediglich das Entschlüsselungs-Problem entsprechend umformulieren.

Da kann man sich schonmal fragen wie das gehen soll, denn möglich wäre es. Wäre wirklich P=NP, dann würde das unser komplettes Weltbild radikal verändern. Wir müssten die gesamte Welt und sämtliche bestehenden Naturgesetze auf einen Schlag mit komplett anderen Augen betrachten. Das alles klingt doch schon extrem merkwürdig und unwahrscheinlich. Darum sind die meisten Informatiker sich heute einig: es muss P≠NP gelten. Nur beweisen konnte das bis heute niemand. Nicht umsonst ist P vs NP eines der sieben Millennium-Probleme, für deren Lösung 1 Mio. US-Dollar Preisgeld angesetzt sind.

Im August 2017 jedoch hat Norbert Blum, ein deutscher Informatik-Professor einen möglichen Beweis für den Fall P≠NP eingereicht, der momentan noch geprüft wird. Sollte dieser Beweis fehlerfrei sein, so wäre damit bestätigt was sowieso vermutet wird. Allerdings haben sich vor ihm bereits viele andere Experten an einem solchen Beweis versucht und sind alle gescheitert. Entweder haben sie schwere Fehler in ihrer Beweisführung gemacht, die ihre Argumentationen komplett zunichte gemacht haben. Oder ihre Beweise waren dermaßen unverständlich, dass niemand sie verstanden hat (und sie höchstwahrscheinlich auch Fehler enthielten).

Update: Norbert Blum hat am 30.08.2017 seinen Beweis um folgenden Kommentar aktualisiert:

The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage.

Dennoch ein spannendes Thema, oder? Falls du gerne mehr dazu hören würdest oder noch offene Fragen hast, dann schreib mir doch unten in den Kommentaren :blush: