Das größte Problem der Informatik: P versus NP

Es gibt sieben mathematische Probleme, die als so schwer und interessant gelten, dass das Clay Mathematics Institute sie zu Millennium-Problemen erklärt hat. Wer eines davon löst, erhält ein Preisgeld von einer Million Dollar. Eines dieser Probleme betrifft auch die Informatik und heißt P-versus-NP-Problem. Lass uns erklären, worum es bei diesem Problem eigentlich geht.

Na ja. Machen wir uns nichts vor, es wird nicht einfach, das zu erklären. Es ist schließlich ein Problem des Jahrtausends. Also koch dir einen guten grünen Tee 🍵 und legen wir los. Zuerst zeigen wir vier verschiedene Probleme aus der Welt der Informatik und der Algorithmen. Wir analysieren die Probleme und schauen uns an, in welcher Beziehung sie zu den Buchstaben P und NP stehen.

Problem Nr. 1: Die kleinste Zahl finden

P vs. NP betrifft Algorithmen und ihre Komplexität. Stell dir vor, ich würde hundert Zettel vor dir ausschütten, auf jedem steht eine Zahl, und ich wollte, dass du mir den Zettel mit der kleinsten Zahl heraussuchst. Wie lange brauchst du dafür?

Eine halbe Minute? Zwei Minuten?

Das sind Zeiteinheiten, die uns in der theoretischen Informatik nicht so sehr interessieren. Uns interessiert eher die Anzahl der Operationen. Wir könnten also etwas anders fragen: Wie viele Zettel muss ich prüfen, um sicher zu sein, dass ich die kleinste Zahl gefunden habe? Die Antwort lautet, dass ich alle Zettel prüfen muss – denn die kleinste Zahl kann auf dem letzten Zettel stehen. Wenn ich hundert Zettel vor dich werfe, musst du hundert Zettel prüfen. Wenn ich dir tausend gebe, musst du tausend prüfen. Allgemein gilt: Wenn ich n Zettel vor dich werfe, musst du n Zettel prüfen.

Das nennen wir die Komplexität von Algorithmen. Wenn ich n Zettel vor dich werfe und du n Operationen durchführen musst, um die kleinste Zahl zu finden, bedeutet das, dass dieser Algorithmus zum Finden der kleinsten Zahl die Komplexität n hat. Wir nennen das auch lineare Komplexität, weil die Komplexität durch eine lineare Funktion beschrieben wird.

Gut, du hast die hundert Zettel durchgesehen und verkündet, dass die kleinste Zahl 17 ist. Wie kann ich überprüfen, ob du die Wahrheit sagst? Es gibt keine andere Möglichkeit, als wieder alle Zettel durchzugehen und zu prüfen, dass auf keinem eine kleinere Zahl steht. Du musst also n Zettel ansehen, um die kleinste Zahl zu finden, und ich muss, wenn ich es kontrollieren will, dasselbe tun. Die Komplexität der Überprüfung des Ergebnisses ist also ebenfalls n, lineare Komplexität.

Gibt es Algorithmen, bei denen es einfacher ist, das Ergebnis zu überprüfen, als es zu finden?

Problem Nr. 2: Produkt eines Paares

Stell dir vor, ich schütte zwei gleich große Stapel Zettel vor dir aus, auf jedem Zettel steht wieder eine Zahl. Und jetzt möchte ich, dass du eine Zahl aus Stapel A und eine Zahl aus Stapel B findest, deren Produkt die Zahl 918 ergibt. Als Beispiel nehmen wir diese Stapel von Zahlen:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Wie können wir ein Zahlenpaar finden, dessen Produkt gleich 918 ist? Nun, wir können einfach alle Möglichkeiten ausprobieren. Wie viele sind das? Ziemlich viele, nämlich 25. Wir beginnen damit, dass wir die erste Zahl aus Stapel A, also die Zahl 49, mit jeder Zahl aus Stapel B multiplizieren:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Kein Zahlenpaar ergibt 918. Wir versuchen also dasselbe mit den restlichen Zahlen aus Stapel A, also fünf weitere Paare für die Zahl 11, fünf weitere Paare für die Zahl 32, fünf weitere Paare für 54 und die letzten fünf Paare für 15. Insgesamt können wir so 25 Zahlenpaare ausprobieren. Am Ende stellen wir fest, dass 54 · 17 = 918 gilt.

Wie groß ist die Komplexität dieses Algorithmus? Uns interessiert, wie viele Zahlenpaare wir multiplizieren mussten. Beide Stapel enthielten fünf Zettelchen und wir mussten jede der fünf Zahlen des ersten Stapels mit jeder der fünf Zahlen des zweiten Stapels probieren. Insgesamt haben wir 5 · 5 = 25 Kombinationen ausprobiert. Wenn ich zwei Stapel mit je 10 Zetteln vor dich werfen würde, müsstest du 10 · 10 = 100 Kombinationen ausprobieren. Verallgemeinert: Wenn ich zwei Stapel mit je n Zetteln vor dich werfe, musst du n · n = n² Kombinationen ausprobieren.

Wir sagen, dass unser Algorithmus die Komplexität n² hat, quadratische Komplexität, weil sie durch eine quadratische Funktion beschrieben wird.

Wie aufwendig ist es aber, das Ergebnis zu überprüfen? Wenn du mir antwortest, dass 54 und 17 Zahlen sind, deren Produkt 918 ergibt, muss ich nicht mehr alle Zahlenpaare aus beiden Stapeln durchgehen, wie du es tun musstest. Es genügt, dieses eine Paar 54 · 17 zu multiplizieren, und ich weiß, ob du recht hast oder nicht. Während also zum Lösen dieses Problems bis zu n² Produkte berechnet werden müssen, genügt zum Überprüfen die Berechnung eines einzigen Produkts. Die Überprüfung hat also konstante Komplexität 1.

Dadurch unterscheidet sich diese Aufgabe deutlich von der vorigen, bei der wir für die eigentliche Berechnung und für die anschließende Überprüfung gleich viele Schritte brauchten.

Diese Aufgabe ist außerdem der Größenordnung nach schwieriger als die vorige. Wenn ich zehntausend Zettel vor dir ausschütten würde und du die kleinste Zahl finden solltest, könntest du sie wahrscheinlich an einem Tag finden. Würde ich aber zweimal zehntausend Zettel vor dir ausschütten und dich ein Produkt suchen lassen, müsstest du zehntausend mal zehntausend Produkte prüfen, das sind hundert Millionen Berechnungen. Selbst wenn du ein Produkt pro Sekunde ausprobieren würdest, würde dich das etwa drei Jahre kosten.

Problem Nr. 3: Teilsummenproblem

Schauen wir uns das dritte Problem an. Diesmal schütte ich zwölf Zettel mit Zahlen vor dir aus und möchte, dass du eine beliebige Anzahl von Zetteln findest, deren Summe null ergibt. Als Beispiel:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Wähle aus diesen Zahlen eine beliebige Gruppe von Zahlen aus, deren Summe null ergibt. Zum Beispiel die Zahlen

$24 + 48 - 69 + 1$

ergeben die Summe 4 und sind daher nicht die richtige Antwort. Die richtige Antwort ist die Gruppe von Zahlen … und weißt du was? Versuch sie als Hausaufgabe selbst zu finden 😉. Es gibt genau eine Gruppe von Zahlen, deren Summe 0 ergibt. Dabei merkst du zumindest, wie schwer dieses Problem ist.

Jetzt müssen wir die Komplexität dieses Problems kennen. Die eigentliche Berechnung ist nicht ganz trivial und eher etwas für Feinschmecker. Wenn dich also interessiert, wie man die Komplexität dieses Problems berechnen kann, lies weiter. Sonst kannst du zum nächsten Kapitel springen. ⏩

Wie können wir also eine Gruppe von Zahlen finden, deren Summe 0 ergibt? Nun, wir müssen einfach alle möglichen Kombinationen von Zahlen ausprobieren. Wir müssen alle Zahlenpaare, alle Dreiergruppen, Vierergruppen, Fünfergruppen usw. ausprobieren und bei jeder Gruppe prüfen, ob ihre Summe null ergibt. Wie viele solcher Kombinationen gibt es?

Zeigen wir es an einer kleineren Menge von Zahlen. Wie viele verschiedene Gruppen von Zahlen, also Teilmengen, kann ich aus den drei Zahlen B = {5, 7, 9} bilden? Es sind insgesamt acht:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Beachte, dass wir auch die leere Teilmenge B₁ mitgezählt haben. Sie ist jetzt nicht besonders nützlich, aber der Ordnung halber haben wir sie dort gelassen. Um die Berechnung zu vereinfachen, ordnen wir jeder Teilmenge einen Binärvektor zu. Ein Binärvektor ist einfach eine Folge von Nullen und Einsen, zum Beispiel 00101010. Wir arbeiten mit Binärvektoren der Länge drei. Den Vektor ordnen wir so zu: 101 ordnen wir der Teilmenge zu, die „die erste und die dritte Zahl der ursprünglichen Menge, aber nicht die zweite Zahl“ enthält, also der Menge {5, 9}. Den Vektor 110 ordnen wir der Teilmenge zu, die „die erste und die zweite Zahl der ursprünglichen Menge, aber nicht die dritte“ enthält, also der Menge {5, 7} usw.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Wir sehen, dass jede Teilmenge genau einen Binärvektor der Länge drei hat. Und jeder Binärvektor der Länge drei entspricht genau einer Teilmenge. Wenn wir also berechnen, wie viele verschiedene Binärvektoren der Länge n es gibt, erhalten wir die Anzahl der verschiedenen Kombinationen, die wir zusammenstellen können, wenn wir n verschiedene Zahlen als Eingabe haben. Rechnen wir das also aus.

Binärvektoren der Länge eins gibt es zwei: 0 und 1.

Binärvektoren der Länge zwei erhalten wir, indem wir alle Binärvektoren der Länge eins nehmen und an das Ende jedes Vektors eine 0 anhängen: Wir erhalten die Vektoren 00 und 10. Wieder nehmen wir alle Vektoren der Länge 1 und hängen am Ende eine 1 an: 01 und 11. Damit haben wir alle Vektoren der Länge 2: 00, 01, 10 und 11.

Binärvektoren der Länge drei erhalten wir, indem wir alle Binärvektoren der Länge zwei nehmen und am Ende eine Null anhängen: 000, 010, 100 und 110 und eine Eins: 001, 011, 101 und 111.

Und so weiter für jede weitere Länge. Wir sehen, dass sich die Anzahl der verschiedenen Binärvektoren verdoppelt, wenn wir die Länge des Binärvektors um eins erhöhen. Für die Vektorlänge vier erhielten wir also insgesamt 2 · 2 · 2 · 2, das ist 16, verschiedene Kombinationen.

Allgemein können wir herleiten: Wenn wir eine Menge M mit n Elementen haben, dann ist die Anzahl aller Teilmengen dieser Menge M gleich der Anzahl aller verschiedenen Binärvektoren der Länge n und diese ist gleich

$\underset{n -mal}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ oder n² – ist das nicht egal? Jacke wie Hose 🤷‍♂

Es gibt also 2ⁿ verschiedene Teilmengen, die wir aus einer Menge von n Zahlen bilden können. In unserem Fall haben wir n = 12 Zahlen und müssen daher 2¹² verschiedene Kombinationen prüfen, das sind 4096 Kombinationen. Wir sagen, dass dieses Problem die Komplexität 2ⁿ hat, exponentielle Komplexität, weil sie durch eine Exponentialfunktion beschrieben wird.

Beachte, dass das vorige Problem die Komplexität n² hatte, während dieses die Komplexität 2ⁿ hat. Das sieht sehr ähnlich aus, oder? Es ist aber ein großer Unterschied, ob der Exponent konstant ist oder ob dort die Variable n steht. Für n = 4 erhalten wir

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Gut, bisher kommt dasselbe heraus. Und was ist für n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Huch, die Exponentialfunktion ist uns davongeschossen und ist plötzlich etwa zehnmal größer als die quadratische. Was erhalten wir für n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

Die exponentielle Komplexität hat für n = 20 einen etwa 2600-mal höheren Wert als die quadratische Komplexität. Wir sehen also, dass die Exponentialfunktion viel schneller wächst als die quadratische Funktion. Denk daran, wenn uns wieder einmal eine Pandemie trifft, die sich in der Bevölkerung exponentiell ausbreitet.

Wenn ich also zwanzig Zettel vor dich werfen würde, müsstest du 1.048.576 Kombinationen prüfen. Das ist ziemlich viel.

Wie überprüfen wir die Richtigkeit des Ergebnisses?

Wie lange brauche ich, um zu überprüfen, dass die gefundene Gruppe von Zahlen wirklich die Summe 0 ergibt? Das geht ziemlich schnell: Ich addiere einfach diese eine Gruppe von Zahlen, und wenn ihre Summe gleich 0 ist, hast du die richtige Gruppe von Zetteln gefunden, wenn die Summe anders ist, hast du die falschen Zettel gefunden.

Wieder sehen wir, dass es der Größenordnung nach einfacher ist, ein Ergebnis zu überprüfen, als es zu finden.

Problem Nr. 4: Problem des Handlungsreisenden

Das Problem des Handlungsreisenden ist eines der berühmtesten algorithmischen Probleme. Grob gesagt haben wir einen Handlungsreisenden, der Regen verkauft. Und dieser Handlungsreisende muss viel reisen, um sich seinen Lebensunterhalt zu verdienen. Deshalb hat er beschlossen, jede Regionshauptstadt in Tschechien zu besuchen. Und weil er nichts verschwenden will, hat er beschlossen, den kürzestmöglichen Weg zu finden, der ihn durch alle Regionshauptstädte des Landes führt. Und unsere Aufgabe ist es, diesen kürzesten Weg zu finden.

Wie können wir diesen kürzesten Weg finden? Wir probieren alle Möglichkeiten aus.

Wir können es uns vereinfachen. Stellen wir uns vor, dass es zwischen je zwei Regionshauptstädten genau einen kürzesten Weg gibt. Wie können wir den kürzesten Weg durch alle Städte finden? Wir haben 14 Regionshauptstädte. Wir haben also 14 Möglichkeiten, wo wir beginnen. Sagen wir, wir haben in Ostrava begonnen!!! Wohin können wir von Ostrava aus gelangen? Theoretisch können wir in jede andere Regionshauptstadt fahren. Wir können also aus den 13 übrigen Städten wählen.

Schon jetzt können wir ausrechnen, dass wir insgesamt 14 · 13 Möglichkeiten haben, die ersten beiden Regionshauptstädte zu besuchen – wir haben 14 Möglichkeiten, wo wir beginnen, und dann die Wahl aus 13 übrigen Regionshauptstädten.

Wenn wir in der zweiten Stadt ankommen, müssen wir weiterfahren. In zwei Städten waren wir schon, also können wir in eine der 12 übrigen Städte reisen. Wir haben so insgesamt 14 · 13 · 12 Möglichkeiten, die ersten drei Städte zu besuchen.

Wenn wir die dritte Regionshauptstadt besucht haben, müssen wir eine der 11 übrigen Städte auswählen, dann eine der 10 übrigen Städte usw.

Wenn wir alle besucht haben, stellen wir fest, dass wir insgesamt aus

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

Möglichkeiten wählen konnten. Das erinnert dich vielleicht an die Fakultät, die wir mit einem Ausrufezeichen bezeichnen. Wir können also sagen, dass dieses Produkt gleich 14! ist:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

und es gibt also 14! Wege, die durch alle Regionshauptstädte in Tschechien führen. Ist das viel? Ziemlich, denn

$14! = 87 178 291 200.$

Allgemein müssten wir, wenn wir den kürzesten Weg zwischen n Städten suchen, n! verschiedene Wege ausprobieren. Die Komplexität dieser Lösung ist also n!.

Wie würden wir überprüfen, dass wir das richtige Ergebnis gefunden haben? Wenn du mir sagen würdest, dass der kürzeste Weg von Plzeň nach Ostrava, dann nach Brno usw. führt, wie kann ich überprüfen, ob du die Wahrheit sagst? Na ja, nur schwer 🤷‍♂. Denn wenn ich mir diesen Weg ansehe, habe ich keine einfache Möglichkeit zu überprüfen, ob gerade dieser Weg der kürzeste ist. Ich muss eigentlich die ganze Berechnung noch einmal durchführen. Die Überprüfung des Ergebnisses hat also ebenfalls die Komplexität n!.

Die Klassen P und NP

Wir haben vier Probleme und die Algorithmen, die sie lösen, vorgestellt und analysiert, wie aufwendig es ist, eine Lösung zu finden und wie aufwendig es ist, diese Lösung zu überprüfen. Wir können das in dieser Tabelle zusammenfassen:

Problem	Komplexität der Lösung	Komplexität der Überprüfung
Kleinste Zahl	n	n
Produkt eines Paares	n²	1
Teilsumme	2ⁿ	n
Handlungsreisender	n!	n!

Nun teilen wir unsere Probleme in zwei Gruppen ein. Die erste Gruppe bilden Probleme, die einfach zu lösen sind. Das sind Probleme, die sich mit der Komplexität n oder n² oder n³ oder n⁴ usw. lösen lassen. Da wir Terme wie n² Polynome nennen, bezeichnen wir diese Klasse von Problemen mit dem Buchstaben P. Wir sagen also, dass die Klasse P die Probleme enthält, die sich in polynomieller Laufzeit lösen lassen (= sie haben zum Beispiel die Komplexität n² oder n⁷). Allgemein sind das Probleme, die sich mehr oder weniger einfach lösen lassen.

In die Klasse P gehört also Problem Nr. 1, das Finden der kleinsten Zahl, weil es die Lösungskomplexität n hat, und dann gehört dazu Problem Nr. 2, das Produkt eines Paares, weil seine Lösungskomplexität n² ist, was beides Polynome sind.

Die zweite Klasse ist die Klasse NP. Sie enthält Probleme, die sich in polynomieller Laufzeit überprüfen lassen. In die Klasse NP gehören also alle Probleme außer dem letzten. Das Problem des Handlungsreisenden können wir nicht in polynomieller Laufzeit überprüfen. Die vorigen drei Probleme lassen sich in polynomieller Laufzeit überprüfen.

Das Problem des Handlungsreisenden können wir weder in polynomieller Laufzeit lösen noch überprüfen. Für das Problem des Handlungsreisenden bräuchten wir also noch eine weitere Klasse, die noch schwierigere Probleme enthält. Diese Klasse gibt es, aber sie ist für uns im Moment nicht interessant.

Offensichtlich ist die Klasse P eine Teilmenge der Klasse NP. Das heißt, jedes Problem, das in der Klasse P liegt, liegt zugleich in der Klasse NP. Das ergibt Sinn – wenn wir ein Problem in polynomieller Laufzeit lösen können, können wir das Ergebnis auch in polynomieller Laufzeit überprüfen.

Das P-NP-Problem

Und gilt das auch umgekehrt? Liegt jedes Problem aus der Klasse NP zugleich auch in der Klasse P? Also: Wenn es eine Möglichkeit gibt, das Ergebnis eines Problems in polynomieller Laufzeit zu überprüfen, gibt es dann auch einen Algorithmus, der das Problem in polynomieller Laufzeit lösen würde?

Zum Beispiel wissen wir, dass wir das Ergebnis von Problem Nr. 3, dem Teilsummenproblem, in polynomieller Laufzeit überprüfen können. Aber zu seiner Lösung haben wir einen Algorithmus verwendet, der nicht polynomiell ist, der verwendete Algorithmus hat die exponentielle Komplexität 2ⁿ. Wissen wir aber sicher, dass es für dieses Problem keinen Algorithmus mit polynomieller Komplexität gibt?

Wir wissen es nicht!

Es könnte durchaus sein, dass es für jedes Problem, das sich in polynomieller Laufzeit überprüfen lässt, einen Algorithmus gibt, der dieses Problem in polynomieller Laufzeit löst. Wir wissen es nicht. Wir können die Existenz eines solchen Algorithmus nicht beweisen, aber wir können seine Existenz auch nicht widerlegen.

Wenn es für jedes Problem aus der Klasse NP einen Algorithmus gäbe, der es in polynomieller Laufzeit löst, würde das bedeuten, dass die Klasse NP eigentlich gleich der Klasse P wäre. Alle Probleme aus der Klasse P wären in der Klasse NP und alle Probleme aus der Klasse NP wären in der Klasse P – beide Klassen wären gleich, sie wären identisch.

Das P-NP-Problem ist also die Frage, ob die Klasse P mit der Klasse NP identisch ist oder ob es sich um zwei verschiedene Klassen von Problemen handelt.

Entweder gilt also P = NP oder es gilt P ≠ NP. Das weiß niemand, und wenn du es herausfindest, erwartet dich ein Preisgeld von einer Million Dollar, unvergänglicher Ruhm und wahrscheinlich auch der Turing Award, das ist so etwas wie der Nobelpreis für Informatiker.

Was würde passieren, wenn P = NP gälte?

Was würde passieren, wenn P = NP gälte? Nun, es ist nicht ganz einfach zu sagen, was passieren würde. Wir wüssten, dass es für alle Probleme aus der Klasse NP einen Algorithmus gibt, der sie in polynomieller Laufzeit löst. Zum Beispiel, dass es für unser Problem Nr. 3, das Teilsummenproblem, einen Algorithmus gibt, der es in polynomieller Laufzeit löst. Das hat aber drei Haken:

Dass wir wüssten, dass ein solcher Algorithmus existiert, heißt nicht, dass wir ihn auch finden können. Wir würden einfach wissen, dass ja, es gibt einen Algorithmus, der das Problem in polynomieller Laufzeit löst, aber wir könnten ihn vielleicht noch hundert Jahre lang nicht konstruieren. Das ist ähnlich wie bei der allgemeinen Relativitätstheorie, die die Existenz von Schwarzen Löchern vorhersagte, und trotzdem dauerte es noch mehrere Jahrzehnte, bis wir das erste „Foto“ eines Schwarzen Lochs aufnehmen konnten.
Dass es einen Algorithmus gibt, der in polynomieller Laufzeit arbeitet, bedeutet leider noch nicht, dass er schnell ist. Wir könnten einen Algorithmus finden, der die Komplexität n¹⁰⁰ hat. Auch der Term n¹⁰⁰ ist nämlich ein Polynom. Wenn wir die Komplexitäten 2ⁿ und n¹⁰⁰ vergleichen, stellen wir fest, dass ein Algorithmus mit der Komplexität 2ⁿ noch weniger Operationen braucht, solange n relativ klein ist. Zum Beispiel gilt für n = 20, dass 2²⁰ = 1.048.576, während der Term 20¹⁰⁰ zu einer Zahl mit etwa 130 Ziffern führt, was eine Zahl ist, die um 120 Größenordnungen größer ist als 1.048.576. Unser polynomieller Algorithmus wäre in der Realität also langsamer als der exponentielle. Zumindest solange n relativ klein ist.
Wenn wir es doch schaffen würden, einen schnellen Algorithmus zu finden, der in polynomieller Laufzeit arbeitet, könnten wir viele Probleme schneller und genauer lösen. Das ist natürlich eine positive Nachricht, hat aber auch seine Schattenseiten. Es gibt ein Gebiet, das sich darauf verlässt, dass manche Probleme schwer lösbar sind, und das ist die Kryptographie – die Verschlüsselung. Es könnte also passieren, dass es der Größenordnung nach einfacher wäre, die heutigen Verschlüsselungen zu knacken.

Intermezzo: Weil du bis hierher gelesen hast, verrate ich dir zur Belohnung, dass die Lösung von Problem Nr. 3 24 + 1 − 60 + 16 − 83 + 48 + 54 ist.

Was würde passieren, wenn P ≠ NP gälte?

Wenn die Problemklassen P und NP verschieden wären, würde sich nicht besonders viel ändern, denn das ist mehr oder weniger der Status quo. Wir haben im Moment keinen Algorithmus, der ein schweres Problem aus NP in polynomieller Laufzeit löst, und wenn jemand beweisen würde, dass P ≠ NP, bliebe das einfach für immer so. Viel sensationeller wäre ein Beweis, dass P = NP.

Verweise in der Popkultur

In einer Folge der Simpsons sehen wir, wie Homer in eine Art alternative Realität gerät, in der ihm offenbart wird, dass P = NP. Zu sehen auf youtube.com.
In Futurama wiederum sehen wir, dass sie im Lager zwei Ordner haben, einen mit der Aufschrift P und einen mit der Aufschrift NP. Zu sehen auf youtube.com.
Die zweite Folge der zweiten Staffel der Serie Elementary mit dem Titel „Solve for X“ handelte vom Mord an einem Mathematiker, der wahrscheinlich das P-versus-NP-Problem gelöst hatte.

« Zurück: Wie viel ist 1 + 2 + 5 · 0? Oder: Punkt vor Strich

Weiter: Exponentialzeithypothese (ETH) »