Zum Inhalt
Alle Apps

P vs. NP

Über diese App

Lösen gegen Prüfen: Eine Clique im Graphen finden heißt Teilmengen durchprobieren (Zähler explodiert), ein Zertifikat prüfen dauert k(k−1)/2 Schritte. Wachstumsszene mit 2ⁿ und n! gegen n³ bis zum Alter des Universums — ein 1000-mal schnellerer Rechner bringt bei 2ⁿ nur zehn Schritte. Landkarte der Klassen P, NP und NP-vollständig in beiden möglichen Welten. Millennium-Problem, 1 Mio. $.

Das Millennium-Problem P = NP?

P ist die Klasse der Probleme, die sich in polynomieller Zeit lösen lassen, etwa Sortieren oder kürzeste Wege. NP enthält die Probleme, deren Lösung sich in polynomieller Zeit prüfen lässt, wenn man sie vorgelegt bekommt. Jedes Problem in P liegt auch in NP. Ob umgekehrt alles schnell Prüfbare auch schnell lösbar ist, ist offen: Das ist die Frage P = NP, eines der sieben Millennium-Probleme des Clay-Instituts mit einer Million Dollar Preisgeld. NP-vollständige Probleme wie SAT oder Clique sind die schwersten in NP: Ein schneller Algorithmus für eines davon würde alle lösen.

Was die App zeigt

Drei Szenen. In „Lösen gegen Prüfen“ sucht die rohe Suche in einem Graphen mit 6 bis 14 Knoten eine Clique der Größe 3 bis 5 und probiert dafür alle Teilmengen durch; ein Zertifikat zu prüfen kostet dagegen nur k(k−1)/2 Kantentests. Die Wachstumsszene vergleicht n², n³, 2ⁿ und n! auf logarithmischer Zeitachse bis zum Alter des Universums. Die Landkarte zeigt P, NP und NP-vollständig mit Beispielen in den beiden möglichen Welten P ≠ NP und P = NP.

Selbst ausprobieren

Stelle Knotenzahl und Cliquengröße ein, lass die Suche laufen und vergleiche den Zähler mit den Prüfschritten. Klicke selbst Knoten an und lass dein Zertifikat prüfen. Schalte in der Wachstumsszene einen 1000-mal schnelleren Rechner zu: Bei 2ⁿ gewinnt man dadurch nur etwa zehn Schritte in n. Auf der Landkarte wechselst du zwischen den beiden Welten.

Häufige Fragen

Was bedeutet P vs. NP einfach erklärt?
Die Frage lautet: Lässt sich jedes Problem, dessen Lösung man schnell überprüfen kann, auch schnell lösen? „Schnell“ heißt dabei: in polynomieller Zeit. Ein Sudoku zu prüfen ist leicht, eines zu lösen scheint im Allgemeinen viel schwerer. Ob es wirklich schwerer ist, weiß niemand.
Was heißt NP-vollständig?
Ein Problem ist NP-vollständig, wenn es in NP liegt und sich jedes andere NP-Problem in polynomieller Zeit darauf zurückführen lässt. Beispiele sind SAT, Clique, Hamiltonkreis und das Rucksackproblem. Fände man für eines einen polynomiellen Algorithmus, wäre P = NP.
Heißt NP „nicht polynomiell“?
Nein. NP steht für nichtdeterministisch polynomiell: Eine vorgeschlagene Lösung lässt sich in polynomieller Zeit prüfen. P ist eine Teilmenge von NP. Ob NP echt größer ist als P, ist die offene Frage.
Was zeigt die P-vs-NP-App?
Eine Cliquensuche, bei der rohes Durchprobieren gegen schnelles Prüfen antritt, eine Wachstumsszene mit 2ⁿ und n! gegen Polynome und eine Landkarte der Komplexitätsklassen, die zwischen den Welten P ≠ NP und P = NP umschaltet.

Fach: Informatik

Mehr aus Informatik

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps