Computatio Difficilis
Observatorium der Unentscheidbaren Komplexität
The Question itself
P ist die Klasse der Probleme, die ein deterministischer Computer in polynomieller Zeit lösen kann. Multiplikation, Sortierung, kürzeste Wege — alles Alltägliche.
NP ist die Klasse der Probleme, deren Lösung in polynomieller Zeit verifiziert werden kann. Finde den Weg durch 30 Städte — schwer. Prüfe ob ein gegebener Weg unter 10.000 km bleibt — einfach.
Die Frage P ≟ NP ist das größte offene Problem der theoretischen Informatik. Ein Preisgeld von einer Million Dollar ruht darauf. Aber es ist mehr als Geld: Wäre P = NP, würde jede mathematische Vermutung, deren Beweis man verifizieren kann, auch findbar sein.
Es gilt wahrscheinlich P ≠ NP. Die Welt würde sonst kollabieren: Verschlüsselung wäre wertlos, KI wäre allwissend, Kreativität wäre Automatisierung.
SAT — The Mother of All Problems
SAT war das erste Problem, das Stephen Cook 1971 als NP-vollständig nachwies. Der Cook-Levin-Satz: Jede Sprache in NP lässt sich in polynomieller Zeit auf SAT reduzieren.
Eine Boolesche Formel in konjunktiver Normalform (CNF): Klauseln von Literalen, verknüpft durch AND. Die Frage: Gibt es eine Belegung der Variablen, die die Formel wahr macht?
Klicke die Variablen an, um die Klauseln zu bewerten. Grün = erfüllt. Rot = nicht erfüllt. Das Ziel: Alle grün.
The Reduction Chain
3-SAT ist SAT mit der Einschränkung: Jede Klausel hat genau drei Literale. Es ist NP-vollständig — und der Dreh- und Angelpunkt fast aller NP-Vollständigkeitsbeweise.
Der Grund: 3-SAT lässt sich auf fast alles reduzieren. Die Kette der Reduktionen verbindet scheinbar unzusammenhängende Probleme zu einem einzigen Geflecht.
Jeder Pfeil ist ein polynomielle Reduktion: Eine Instanz des linken Problems wird in eine Instanz des rechten Problems transformiert, sodass die Antwort erhalten bleibt.
TSP — The Traveling Salesman
TSP: Gegeben n Städte und Distanzen d(i,j). Gibt es eine Rundreise, die jede Stadt genau einmal besucht und unter einer gegebenen Länge k bleibt?
Der Greedy-Algorithmus (immer die nächste Stadt) findet schnell eine Tour — aber nicht die kürzeste. Für 25 Städte gibt es 24!/2 ≈ 3×10²³ Möglichkeiten. Selbst ein Supercomputer bräuchte Jahrmilliarden.
Klicke Regenerate, um neue Städte zu erzeugen. Die Animation zeigt eine nahe optimale Tour (2-Approximation via MST) — nicht die beste, aber in polynomieller Zeit berechenbar.
Clique & Independent Set
Clique: Enthält ein Graph eine vollständige Untergruppe von mindestens k Knoten? Independent Set: Gibt es k Knoten, die keine Kante teilen?
Die beiden Probleme sind dual: Eine Clique in G ist ein Independent Set im Komplement-Graphen. Beide sind NP-vollständig, beide reduzieren aufeinander.
Die Reduktion von 3-SAT auf Clique ist elegant: Für jede Klausel erzeugt man drei Knoten (die Literale). Kanten verbinden nur konsistente Literale aus verschiedenen Klauseln. Eine k-Clique entspricht einer erfüllenden Belegung.
Klicke auf Knoten, um eine Clique zu bilden. Zwei verbundene Knoten = gültige Clique.
The Complexity Landscape
Wenn P ≠ NP (was fast alle glauben), existiert eine ganze Hierarchie zwischen den beiden Klassen. NP-intermediate Probleme wie Faktorisierung und Graph-Isomorphie liegen wahrscheinlich genau dort — weder in P noch NP-vollständig.
PSPACE enthält alle Probleme, die mit polynomiellem Speicher lösbar sind — inklusive NP. EXPTIME braucht exponentielle Zeit. Die echte Hierarchie vermutet: P ⊊ NP ⊊ PSPACE ⊊ EXPTIME.
Das Schöne: Selbst wenn P ≠ NP, sind viele NP-harte Probleme in der Praxis handhabbar. SAT-Solver (z.B. Glucose, Kissat) lösen Millionen von Variablen. TSP-Instanzen mit 10.000 Städten sind lösbar. Die Theorie sagt "schwer" — die Praxis sagt "machbar".