The P versus NP Problem


This article is written in German, my native language. If you’re using Google Chrome, you can right-click anywhere on the page and click “Translate to [Your Language]” until I find the time to translate this article into English.

Das Problem P vs NP ist ein Problem aus der Komplexitätstheorie. In der Komplexitätstheorie untersucht man diejenigen 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 Menge von befragten Menschen zu, dass die gezeigte Person schön ist?” lässt sich hingegen sehr wohl von einem Computer entscheiden. Dazu befragt man einfach einige Menschen und prüft, ob das ausgewertete Ergebnis einen vorher festgelegten Schwellenwert überschreitet.

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. Ja-Nein-Fragen. Wir müssen unsere Beispielprobleme daher erst noch entsprechend umformulieren zu “Ist Zahl X durch 3 teilbar, ja oder nein?”, “Ist das Ergebnis Y das Quadrat der Startzahl X, ja oder nein?” und “Entspricht die vom Algorithmus gelieferte Liste B der korrekten Sortiertung der ursprünglichen Liste A, ja oder nein?”. Da die Probleme in ihrer ursprünglichen Formulierungen bereits effizient lösbar waren 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 das Quadrat von X bildet und es mit Y vergleicht bzw. eine Liste A korrekt sortiert und mit Liste B vergleicht. Ist ein Problem einfach lösbar, so nennt man das Problem auch “in Polynomialzeit lösbar”, d.h. 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 also abgehakt. Was ist mit den übrigen Problemen? Sind das im Umkehrschluss automatisch die schwierigen Probleme? Nein, sind sie nicht! Vergiss nicht, wie wir einfache Probleme definiert haben. Ein Problem ist genau dann einfach, wenn es für alle möglichen Eingabewerte (egal welche) effizient lösbar ist. Ein Beispiel wäre das Problem PRIMES, also der Primzahltest. Dabei handelt es sich um das Entscheidungsproblem “Ist Zahl X eine Primzahl, ja oder nein?”. Früher konnte man zwar für sehr viele Zahlen entscheiden, ob es sich um eine Primzahl handelt, aber nicht für alle. Für kleine Zahlen bekommt man es noch im Kopf hin, bis zu einer gewissen Grenze bekam es ein Computer auch noch hin, doch für Zahlen größer als diese Grenze konnte selbst ein Computer das Problem (mit den damaligen Kenntnissen) nicht mehr effizient (oder überhaupt) lösen. Eine solch riesige Zahl hätte eine Primzahl sein können oder auch nicht, wir wussten es einfach nicht. Solange wir aber noch nicht herausgefunden haben, ob wir ein Problem für alle möglichen Eingabewerte effizient lösen können, dürfen wir es nicht in die Kategorie “einfacher” Probleme stecken. Allerdings könnte es ja sein, dass morgen jemand eine brilliante neue Idee hat, mit der wir das Problem nun plötzlich doch für alle Zahlen lösen können. Nur weil ein Problem heute (noch) nicht als einfaches Problem gilt, bedeutet das also nicht, dass das Problem automatisch “schwierig” sein muss. So ist es dann nämlich auch mit dem Problem PRIMES geschehen. Im Jahr 2002 wurde eine neue Methode entdeckt, mittels der ein Computer nun für jede beliebige Zahl—und sei sie noch so groß—in akzeptabler Zeit die Frage nach der Primalität korrekt mit “ja” oder “nein” beantworten kann. Seit PRIMES nun effizient für alle Zahlen lösbar ist, gehört es ebenfalls zur Klasse der “einfachen” Probleme.

Weil die Begriffe “einfach” und “schwierig” aber ziemlich verwirrend sein können—so einfach kann das Problem ja nicht gewesen sein, wenn man Jahrtausende lang nicht auf die Lösung gekommen ist—sollten wir lieber sagen, dass ein Problem grundsätzlich effizient lösbar ist oder eben nicht; dass es von einem heutigen Computer in Polynomialzeit lösbar ist (und damit in Klasse P liegt) oder eben nicht, ganz unabhängig davon, ob wir schon einen konkreten Lösungsalgorithmus gefunden haben oder nicht. Denn sollte morgen jemand eine brilliante neue Idee haben, so wie es bei PRIMES geschehen ist, dann war das Problem ja schon immer grundsätzlich effizient lösbar, wir wussten bloß einfach noch nicht wie. Es ist nicht so, dass ein “schwieriges” Problem zu einem “einfachen” Problem wurde; das Problem ist nicht aus einer Klasse “grundsätzlich nicht effizient lösbar” in eine Klasse “grundsätzlich effizient lösbar” gewandert, sondern war schon immer effizient lösbar, nur blieb uns die Lösung für lange Zeit verborgen. Selbstverständlich könnte auch der andere Fall eintreten, dass ein heute nicht effizient lösbares Problem dermaßen schwierig ist, dass wir niemals auf eine effiziente Lösung für alle Eingabewerte kommen werden, weil es einfach nicht effizient lösbar für alle Eingabewerte ist. Bei einem Problem außerhalb von P können wir uns also weiter fragen, ob es “vielleicht doch in P” liegt (d.h. irgendwann effizient lösbar für alle Eingaben) oder “auf keinen Fall in P” liegt (d.h. definitiv niemals effizient lösbar für alle Eingaben). In der Komplexitätstheorie unterteilen wir Probleme also nicht bloß in “einfach” oder “schwierig”. Einerseits wäre es ja auch irgendwie langweilig, wenn es nur zwei Kategorien gäbe :stuck_out_tongue: Andererseits wäre eine solch naive Unterteilung wie wir am Beispiel PRIMES gesehen haben auch nicht richtig.1

Doch wie sieht ein Problem aus, das nicht in P liegt? In welchen Klassen außer P kann ein Problem noch liegen? Betrachten wir 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 . Genauso können wir die Zahl 6936 zerlegen in . Aber wie sieht es mit unvorstellbar großen Zahlen aus? Zahlen mit so vielen Stellen, dass sie ganze DIN-A4 Blätter füllen? Wie früher bei PRIMES können wir mit unseren derzeitigen Kenntnissen das Problem der Primfaktorzerlegung nicht für genügend große Zahlen, und somit nicht für alle möglichen Zahlen, effizient lösen. Im Gegensatz zu PRIMES kam aber noch niemand auf die bahnbrechende Lösung.2 Betrachten wir nun das zugehörige Entscheidungsproblem, also beispielsweise “Ist die Primfaktorzerlegung von 13260, ja oder nein?”. Selbst wenn wir nicht von selbst auf die Primfaktorzerlegung von 13260 gekommen wären, die umgekehrte Richtung ist extrem einfach. Ob tatsächlich die Primfaktorzerlegung von 13260 ist, kann man effizient überprüfen, indem man das Produkt einfach berechnet und vergleicht, ob dabei 13260 heraus kommt. Dies gilt nicht nur für 13260, sondern für alle Zahlen. Egal wie groß eine Zahl ist, wenn ich dir diese Zahl sowie irgendwelche Faktoren nenne, dann kannst du ganz einfach bestätigen oder widerlegen, ob es sich um die zugehörige Primfaktorzerlegung handelt. Erstens mal müssen alle Faktoren natürlich Primzahlen sein. Zweitens muss ihr Produkt die genannte Zahl ergeben. Wir sehen also: obwohl sich das Entscheidungsproblem Primfaktorzerlegung zwar nicht effizient für alle möglichen Zahlen lösen lässt, lässt es sich dennoch 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 ist offensichtlich eine Teilmenge 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. Deswegen darf man sich die verschiedenen Klassen auch nicht wie Schubladen oder Ordner vorstellen, welche häufig zur Erklärung herangenommen werden. Denn Schubladen implizieren, dass ein Problem nur genau einer Klasse zugehörig sein kann. Vielmehr muss man sich die Klassen wie Aufkleber oder Tags vorstellen. Kann ich jede beliebige gegebene Lösung eines Problems in Polynomialzeit überprüfen, so bekommt das Problem den Aufkleber NP. Funktioniert die umgekehrte Richtung ebenfalls in Polynomialzeit (für alle Eingabewerte), so bekommt das Problem zusätzlich den zweiten Aufkleber für P.3 Es ist nicht so, dass ein Problem plötzlich eine Wanderung von einer Schublade in die andere unternimmt, in dem Moment in dem seine Zugehörigkeit zur Klasse P bewiesen wurde. Das Problem bleibt vielmehr genau dort, wo es schon immer war, und bekommt lediglich einen weiteren Aufkleber (Reminder: aus “schwierig” wurde nicht plötzlich “einfach”, es war schon immer “einfach”, lediglich unsere Betrachtungsweise hat sich geändert).

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. Beispielsweise kann man das Quadrieren einer Zahl ja auch mit dem Algorithmus zur Multiplikation zweier Zahlen lösen; in dem Fall multipliziert man eine Zahl eben 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? Betrachten wir ein anderes Problem, welches zwar innerhalb von NP liegt, aber nicht erwiesenermaßen in P: das mit derzeitigem Kenntnisstand unlösbare Faktorisierungsproblem. Das Faktorisierungsproblem ist die Grundlage unserer heutigen RSA-Verschlüsselung. Es liegt in NP, da wir zwei gegebene Primzahlen ohne großen Aufwand miteinander multiplizieren und mit der in Primfaktoren zu zerlegenden Zahl vergleichen können. Die Gegenrichtung hingegen ist für genügend große Zahlen wieder extrem schwierig, sprich mit heutigen Mitteln unmöglich. Unvorstellbar große Zahlen können selbst von den schnellsten heutigen Computern nicht in zwei Primzahlen zerlegt werden, so dass genau die beiden Primzahlen herauskommen, die sich jemand anderes ausgedacht hat, um sie überhaupt erst zu der unvorstellbar großen Zahl zu multiplizieren. Wir können allerdings weder sicher sagen, dass das Problem in P liegt, noch können wir sicher sagen, dass es nicht in P liegt. Im Fall, dass es in P liegt, müssten wir uns nach einer anderen Verschlüsselungsmethode umsehen. Denn dann wäre das Faktorisierungsproblem ja für alle Zahlen lösbar ist, woraus folgt, dass es nur eine Frage der Zeit ist bis unsere jetzige Verschlüsselung geknackt wird.4 Der andere Fall wäre genauso interessant, denn damit wäre das Faktorisierungsproblem das erste (und bisher einzige) Problem, das in NP, aber definitiv nicht in P liegt. Damit wäre bewiesen und unsere heutigen Verschlüsselungsverfahren wären für alle Zeiten sicher. Wäre hingegen , so wären sämtliche Probleme aus NP, die heute noch ungelöst sind und “schwierig” erscheinen, in Wirklichkeit alle einfach und wir haben lediglich noch nicht die bahnbrechende Idee gehabt. Falls , so würde es jedem Problem in NP so ergehen wie PRIMES. Damit wäre nicht nur unsere Verschlüsselung gebrochen. Damit hätten wir den Beweis, dass für sämtliche Probleme, an denen Computer heutzutage noch Millionen von Jahren rechnen müssten, wie z.B. die Primfaktorzerlegung oder das Traveling Salesman Problem, bahnbrechende Lösungen existieren, die nur darauf warten gefunden zu werden.

Was gilt nun, oder ? Es wird vermutet, dass . Denn wäre , dann wäre es doch naheliegend, dass im Laufe der gesamten Menschheitsgeschichte von irgendeinem der vielen Menschen dieser Erde doch irgendjemand schon einmal für zumindest eines der vielen, angeblich so einfachen, Probleme einen Lösungsansatz gefunden hätte (hier einige Beispiele für Probleme in NP, aber nicht sicher in P). Falls , so gäbe es kein (Entscheidungs)problem, das in NP liegt, aber nicht in P. Gleichzeitig würde das bedeuten, dass alle NP-vollständigen Probleme in P liegen und weiterhin jedes Problem in P auch NP-vollständig ist—siehe folgendes Mengendiagramm (Quelle).

Mengendiagramm der möglichen Beziehungen zwischen P, NP und den Mengen der NP-schweren und NP-vollständigen Probleme.

Und das würde wiederum bedeuten, dass sich jedes Problem in NP so umformulieren ließe, dass es sich von jedem beliebigen, bereits heute bekanntem, effizienten Algorithmus lösen lassen ließe. Jedes beliebige Problem ließe sich also 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 schon fragen, wie das denn bitte gehen soll. Möglich wäre es jedenfalls, falls .

Falls 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 sich die meisten Informatiker heute einig: es muss 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 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 höchstwahrscheinlich auch Fehler enthielten).

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:

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.

  1. Eine sehr schwammige alternative Erklärung: versucht sich ein totaler Anfänger einer neuen Fremdsprache direkt an Hausaufgaben aus dem Sprachkurs einer höheren Niveaustufe (z.B. B1), erscheinen ihm diese subjektiv betrachtet schwierig. Wird derjenige nach einigen Jahren flüssiger in der Sprache und erlangt die nötigen Kenntnisse, erscheinen ihm die alten Hausaufgaben plötzlich einfach. Die Hausaufgaben wurden aber nicht von “schwierig” zu “einfach”. Objektiv betrachtet (im Vergleich zu anderen Hausaufgaben aus einem C2-Kurs) waren sie schon die ganze Zeit einfach. 

  2. Vielleicht ändert sich das ja eines Tages, sobald Quantencomputer Marktreife erreichen. Ein Quantencomputer könnte das ähnliche, heute noch nicht effizient lösbare Faktorisierungsproblem beispielsweise mit dem Shor-Algorithmus in Polynomialzeit lösen. Zur Faktorisierung einer Zahl n benötigt ein Quantencomputer allerdings mindestens log(n) Qubits—und heutzutage existieren erst Quantencomputer mit 50 Qubits. In der Praxis ist der Shor-Algorithmus also noch nicht anwendbar. 

  3. Wir hatten ja gesagt, dass ein Problem in P liegt, wenn es von einem heutigen Computer in Polynomialzeit gelöst werden kann. Eine häufige Fehlannnahme ist jetzt, dass Leute denken, NP würde Nicht-Polynomial bedeuten und dass ein heutiger Computer das Problem vermutlich nicht in Polynomialzeit lösen kann. Das ist aber falsch, denn Probleme in P liegen ja ebenfalls in NP—ein Computer soll das Problem also in akzeptabler Zeit lösen können, gleichzeitig aber auch nicht!? Die Bezeichnung “NP” hat einen anderen Ursprung. Dazu muss man wissen, dass unsere heutigen Computer auf dem Rechenmodell der Turingmaschine basieren, und zwar auf der deterministischen Turingmaschine. Diese kann immer nur einen möglichen Lösungsweg gleichzeitig ausprobieren und muss demnach alle in Frage kommenden Lösungswege einen nach dem anderen ausprobieren. Fehlen einem die nötigen Kenntnisse für einen geschickten Lösungsweg, kommt das einem Brute-Force-Ansatz gleich. Bei genügend vielen möglichen Lösungswegen führt dieser Ansatz nicht in Polymialzeit zum Ziel. Es gibt aber noch ein anderes Rechenmodell, das allerdings nur in der Theorie, nur in unserer Fantasie, existiert: die nichtdeterministische Turingmaschine. Diese kann alle n möglichen Lösungswege gleichzeitig ausprobieren und kann das Problem daher bereits nach einem einzigen Schritt lösen (und nicht erst im schlimmsten Fall nach n Schritten), weil sie einfach alle Lösungswege ausprobiert und schaut, welcher zum Ziel geführt hat (beispielsweise welche der n Zahlenkombinationen die Verschlüsselung geknackt hat und die verschlüsselte Email lesbar gemacht hat). Eine nichtdeterministische Turingmaschine (die allerdings in der Praxis noch nicht existiert), kann jeden beliebigen Lösungskandidaten in Polynomialzeit bestätigen oder widerlegen—und daher kommt der Begriff NP (Nondeterministic-Polynomial). Aber selbst diese bislang rein theoretische Gedankenmaschine kann die NP-schweren Probleme außerhalb von NP (wie z.B. das Halteproblem) nicht lösen (innerhalb eines annehmbaren Zeitrahmens). Das zeigt schon gut, wie schwierig diese Probleme außerhalb von NP sein müssen. 

  4. Einige Menschen behaupten, dass bereits bewiesen sein könnte, dass das Faktorisierungsproblem in P liegt, unsere Verschlüsselung also bereits geknackt wurde und der Beweis deshalb von den Geheimdiensten zurückgehalten wird.