Komplexitätsklassen erklärt
„NP-schwer“ wird im Alltag als Urteil gelesen: geht nicht. Diese Linie zeigt, was die Einordnung tatsächlich sagt und was nicht. Die Klasse gehört zum Problem, nicht zum Verfahren; NP-schwer heißt nicht, dass jede Instanz schwer ist; und die Einordnung ist der Anfang der Arbeit, denn je nach Grund der Härte gibt es einen anderen Ausweg: Zahlen klein halten, eine Garantie statt des Optimums, einen kleinen Parameter, Zufall oder einen guten Löser. Zehn Stücke gehen diese Wege, jedes an einem Beispiel, das sich noch überblicken lässt.
Gezählt wird überall in Rechenschritten (Zugriffe, Knoten, Zellen), nie in Sekunden, auf erzeugten Beispielen mit festem Zufalls-Seed. Die Klassenzugehörigkeiten selbst (NP-vollständig, PSPACE, W[1], PLS) sind Literatur und werden nicht gemessen; gemessen wird, was die Verfahren auf den Beispielen kosten. Echte Betriebsdaten gehören nicht dazu.
In short: Interactive demos on computational complexity classes and what NP-hardness really means: P versus NP, reductions, SAT phase transitions, pseudo-polynomial algorithms and FPTAS, approximation limits, fixed-parameter tractability, randomized tests, counting, PSPACE games and local search (PLS).
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Zuordnung gegen Rundreise verständlich erklärt
Warum dieselbe Kostentabelle eine Aufgabe trägt, für die es eine Abkürzung gibt (Fahrzeuge Aufträgen zuordnen), und eine, für die man keine kennt (die Rundreise), und was „NP-schwer“ dabei wirklich heißt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die zehn Stücke im Überblick
Wurzel ist der Vergleich zweier Aufgaben mit derselben Kostenmatrix. Von dort führen drei Wege: die Reduktionen (woher die Härte der Rundreise kommt), die Zahlen (Härte, die nur in der Größe der Zahlen steckt) und der Zufall. Aus den Reduktionen folgen die Frage nach den typischen Instanzen (SAT in der Praxis), die Garantie statt des Optimums und, als Kontrast, der kleine Parameter. Das Zählen steht als Gegenstück zum Finden daneben.
Drei Stücke sind Zusammenflüsse: Die Reduktionskette gibt den Lösern der Härte-Reihe Graphen aus Formeln, das Spiel um QBF nimmt die Spielbaum-Verfahren auf, und die lokalen Optima verbinden die Größe der Zahlen mit der Lokalsuche aus der Metaheuristik-Linie.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Der gestrichelte Doppelpfeil ist ein Kontrast (gleiche Eingabe, andere Klasse oder anderer Parameter), gepunktete Pfeile übernehmen nur eine Idee, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Härte und Struktur — Die Reduktionskette baut aus Formeln Graphen und gibt sie den Lösern der Nachbarlinie (Clique, Knotenüberdeckung); die parametrisierte Demo stellt beide Probleme auf demselben Graphen gegenüber, wo es um Struktur statt um Klassen geht.
- Trajektorien-Metaheuristiken — Die Lokalsuche auf Rundreisen bleibt in einem lokalen Optimum stecken; die Demo zu lokalen Optima fragt, wie lang der Weg dorthin sein kann und was darüber entscheidet.
- Adversarische Suche — Das Spiel um quantifizierte Formeln zählt dieselben Knoten wie Minimax und Alpha-Beta und ordnet sie als Platz- und Zeitfrage ein.
- Exakte Suche — Die Tabelle des Rucksacks aus der dynamischen Programmierung ist pseudopolynomiell: Zahlen und Härte macht die Länge der Zahlen zum Regler und rundet sie mit dem FPTAS.
Zuordnung gegen Rundreise: dieselbe Matrix, zwei Klassen
Sehen Sie, warum dieselbe Kostenmatrix zwei verschieden schwere Aufgaben trägt: Fahrzeuge Aufträgen zuordnen bleibt für die Ungarische Methode leicht, die beste Reihenfolge der Orte wird mit jedem Ort um ein Mehrfaches teurer. Die Demo zählt Zugriffe statt Sekunden und fragt, was tausendfache Hardware bringt. Der Haken: Auf den Testmatrizen bleibt die Ungarische Methode weit unter ihrer Schranke für den schlimmsten Fall.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Reduktionskette: 3-SAT, unabhängige Menge, Knotenüberdeckung, Clique
Verfolgen Sie, wie sich eine Erfüllbarkeitsfrage Schritt für Schritt in ein Graphproblem verwandelt: aus Klauseln werden Dreiecke, dann unabhängige Menge, Knotenüberdeckung und Clique, jeweils mit Rückübersetzung der Lösung. Der Haken: Die Reduktion erhält die Antwort, aber nicht die Leichtigkeit. Die Formel ist im Median in höchstens 5 Knoten entschieden, die Überdeckungssuche bricht bei 30 Klauseln in 5 von 5 Fällen am Rechenbudget ab.
Demo starten →SAT in der Praxis: DPLL und Phasenübergang
Sehen Sie, warum 3-SAT trotz NP-Vollständigkeit meist schnell fällt und wo die schweren Formeln liegen: Die Demo erzeugt Zufallsformeln mit wachsendem Verhältnis von Klauseln zu Variablen und zählt die Knoten der DPLL-Suche. Der Haken: Bei den getesteten Schubfach-Formeln macht eine kleine Störung sie leicht, aber nur, weil sie die Antwort ändert; es ist keine Glättung desselben Problems.
Demo starten →Zahlen und Härte: pseudopolynomiell, FPTAS, stark NP-schwer
Verfolgen Sie, was die Größe der Zahlen kostet: Die exakte Tabelle fürs Packen einer Fuhre wird mit jeder zusätzlichen Stelle der Gewichte etwa zehnmal größer. Das FPTAS rundet die Werte und rechnet auf einer Tabelle, die von den Gewichten nicht abhängt. Der Haken: Es lohnt sich erst ab drei bis vier Stellen; bei Gewichten bis 1.000 und feiner Genauigkeit ist die exakte Tabelle kleiner.
Demo starten →Approximation und ihre Grenze: Garantie, Christofides, Nichtapproximierbarkeit
Sehen Sie, was eine Garantie wert ist und wo sie endet: Die Demo vergleicht die Verdopplung des Gerüsts, Christofides und den nächsten Nachbarn auf Rundreisen und zeigt dann, warum beim allgemeinen Rundreiseproblem keine Garantie möglich ist. Der Haken: Die Verdopplung mit Garantie war in dieser Umsetzung bei gleichverteilten Punkten im Median nicht besser als der nächste Nachbar ohne (1,222 gegen 1,124 bei 14 Orten).
Demo starten →Parametrisierte Komplexität: FPT gegen W[1]
Verfolgen Sie, wie sich auf demselben Graphen zwei Fragen stellen lassen: Gibt es k Standorte, die alle Verbindungen abdecken, und gibt es k Standorte, die alle untereinander verbunden sind? Die Demo zählt Suchknoten über Graphgröße und k. Der Haken: FPT heißt nicht immer schneller; auf Zufallsgraphen mit 20 Knoten braucht das Verzweigen bei k gleich 14 im Median 32.767 Knoten, die Cliquensuche 21.
Demo starten →Zufall in der Komplexität: Freivalds, Miller–Rabin, RP und BPP
Sehen Sie, wie ein Zufallstest mit kontrolliertem Fehler billiger prüft, als nachzurechnen: Freivalds ein Matrixprodukt, Miller–Rabin eine Primzahl. Die Demo zählt alle möglichen Zufallswerte, statt zu würfeln, und zeigt, dass der Anteil lügender Werte nie über der Schranke liegt. Der Haken: Für den einfachen Fermat-Test gilt die Schranke nicht, bei den Carmichael-Zahlen bis 50.000 lügen 57,1 % bis 88,9 % der Basen.
Demo starten →Zählen: Permanente gegen Determinante
Verfolgen Sie, warum Zählen schwerer ist als Finden: Die Determinante einer Matrix ist schnell zu haben, die Permanente, die dieselben Produkte ohne Vorzeichen addiert und Paarungen zählt, nicht (bei 20 Zeilen 9.961.472 Multiplikationen nach Glynn gegen 4.940). Der Haken: Die Vorzeichen lassen sich nicht reparieren, schon für die Matrix aus lauter Einsen mit drei Zeilen nicht, und gewürfelte Vorzeichen schätzen nur mit wachsender Streuung.
Demo starten →Platz und Alternierung: QBF als Spiel
Sehen Sie, was ein Gegner kostet: Eine Formel mit abwechselnden Quantoren ist ein Spiel zwischen zwei Seiten, und ein Beweis ist keine Belegung mehr, sondern eine ganze Gewinnstrategie. Die Demo zählt Aufrufe der Tiefensuche und die Größe der Strategie. Der Haken: Das gilt für zufällige Formeln mit abwechselnden Quantoren; bei 18 Variablen besucht die Suche dort nur 0,7 % des Baums.
Demo starten →Lokale Optima finden: PLS
Verfolgen Sie, wie eine Lokalsuche Knoten auf die andere Seite eines Schnitts setzt, bis nichts mehr hilft: Ein lokales Optimum gibt es, weil der Schnitt wächst; offen ist die Länge des Wegs. Die Demo vergleicht vier Wahlregeln und eine Familie mit ungleichen Gewichten. Der Haken: Gemessen an der Schrittschranke braucht sie bei Gewichten bis 1.000 höchstens 0,14 %, bei Gewichten 1 und 10 Knoten aber bis zu 47,4 %.
Demo starten →Mein Problem gilt als schwer, und jetzt?
Ein Entscheidungsbaum über alle zehn Stücke, entlang der Frage, woher die Härte kommt und welchen Ausweg man sucht: große Zahlen, ein Garantiewunsch, ein kleiner Parameter, ein Zufallstest, das Zählen oder ein Gegner im Spiel.
Mein Problem gilt als schwer. Was ist der Grund?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Antworten gelten für die erzeugten Beispiele der Demos, nicht für jedes Problem. Ob für ein Problem eine Garantie, ein kleiner Parameter oder ein Zufallstest überhaupt existiert, hängt vom Problem ab; die Demos zeigen je einen Fall und keine Zusage, dass der Weg trägt. Die Klassenzugehörigkeiten sind Literatur, gemessen werden Rechenschritte.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.