Intraktabilität

Wo die Grenze verläuft

Auf der Komplexitäts-Seite ging es um O(n) gegen O(n²). Hier geht es um eine gröbere, aber härtere Grenze: polynomiell (n, n², n³, auch n¹⁰) gegen exponentiell (2ⁿ, n!). Bei einer Milliarde Schritten pro Sekunde:

Das Universum ist etwa 1,4 · 10¹⁰ Jahre alt. Schnellere Hardware hilft bei exponentiellem Aufwand kaum: Ein tausendmal schnellerer Rechner schafft bei 2ⁿ gerade einmal zehn Elemente mehr. Deshalb gilt seit den 1960er-Jahren die Faustregel (nach Cobham und Edmonds): polynomiell heißt handhabbar, exponentiell heißt intraktabel. Ein O(n¹⁰⁰)-Algorithmus wäre zwar kaum praktisch, aber solche kommen bei natürlichen Problemen selten vor.

P und NP genauer

Jedes Problem in P ist auch in NP – wer lösen kann, kann auch prüfen. Die offene Frage ist die Umkehrung: Ist P = NP? Wenn ja, wäre jedes Problem, dessen Lösungen man schnell prüfen kann, auch schnell lösbar. Fast alle Fachleute glauben, dass nicht – aber seit 1971 hat es niemand bewiesen. Wie sich Finden und Prüfen anfühlen, zeigt das folgende Rätsel.

SAT: Finden gegen Prüfen

Eine Formel in konjunktiver Normalform ist eine Liste von Klauseln, die alle erfüllt sein müssen; jede Klausel ist erfüllt, wenn mindestens eines ihrer Literale stimmt. ¬B heißt „B ist falsch“. Finde die Belegung, die alle 14 Klauseln erfüllt – es gibt genau eine:

Das ist der Kern von NP: Prüfen kostet einen Blick auf jede Klausel – das macht der Rechner in Mikrosekunden. Finden heißt im schlimmsten Fall, die 2⁶ = 64 Belegungen durchzuprobieren. Bei 100 Variablen wären es 2¹⁰⁰ ≈ 10³⁰. Das Zertifikat ist die Belegung selbst: kurz, leicht zu prüfen, schwer zu finden.

Cook und Levin: alles ist SAT

Stephen Cook (1971) und unabhängig Leonid Levin zeigten: Die Rechnung einer beliebigen nichtdeterministischen Turingmaschine lässt sich in eine SAT-Formel übersetzen – Variablen für „Feld i enthält zum Zeitpunkt t das Zeichen x“, Klauseln für die Regeln. Die Formel ist genau dann erfüllbar, wenn die Maschine „ja“ sagt. Damit war SAT das erste NP-vollständige Problem. Richard Karp zeigte 1972 für 21 weitere Probleme, dass sich SAT in sie übersetzen lässt – heute sind es tausende.

Reduktion: ein Problem in SAT übersetzen

Ein praktisches Beispiel: Lässt sich eine Landkarte so färben, dass Nachbarländer verschiedene Farben haben? Die Übersetzung in SAT ist mechanisch – eine Variable pro Land und Farbe („Frankreich ist rot“), dazu drei Arten von Klauseln: Jedes Land hat mindestens eine Farbe, höchstens eine Farbe, und Nachbarn haben nicht dieselbe. Färbe selbst oder frag den Solver:

Genau so arbeitet man in der Praxis: Man beschreibt sein Problem – Stundenplan, Paketabhängigkeiten, Schaltkreis – als Formel und überlässt die Suche einem SAT-Solver, an dem Forscher seit Jahrzehnten feilen. Die Übersetzung ist polynomiell; die Schwierigkeit steckt allein im Lösen.

Wie SAT-Solver es trotzdem schaffen

NP-vollständig heißt: Im schlimmsten Fall ist kein schneller Algorithmus bekannt. Praktische Formeln sind aber selten der schlimmste Fall. Der Grundalgorithmus DPLL (Davis, Putnam, Logemann, Loveland, 1962) probiert nicht blind, sondern setzt eine Variable, folgert alles, was daraus zwingend folgt (Unit Propagation: hat eine Klausel nur noch ein offenes Literal, muss es wahr sein), und geht bei einem Widerspruch zurück. Moderne CDCL-Solver (seit Ende der 1990er) lernen zusätzlich aus jedem Widerspruch eine neue Klausel, die denselben Fehler künftig sofort verhindert – damit wurden Instanzen mit Millionen Variablen alltäglich.

Wie schwer eine Formel ist, hängt erstaunlich stark von einem einzigen Verhältnis ab. Bei zufälligen 3-SAT-Formeln mit 25 Variablen:

Wenige Klauseln: fast jede Belegung passt, der Solver ist sofort fertig. Viele Klauseln: Widersprüche zeigen sich schnell. Dazwischen, bei etwa 4,3 Klauseln pro Variable, liegt ein scharfer Übergang – und genau dort sind die Formeln am schwersten. (Bei so kleinen Formeln wie hier verschwimmt der Übergang etwas und die Spitze rutscht leicht nach rechts; je mehr Variablen, desto schärfer wird er.) Das zeigt: „NP-vollständig“ ist eine Aussage über die schwersten Fälle, nicht über die typischen.

Was, wenn P = NP wäre?

Die Folgen wären enorm. Viele Optimierungsprobleme in Logistik, Planung und Chipdesign würden handhabbar, mathematische Beweise ließen sich womöglich automatisch finden. Gleichzeitig hinge die heutige Kryptografie am seidenen Faden: Sie beruht darauf, dass sich Schlüssel schwer finden, aber leicht prüfen lassen. Bemerkenswert dabei: Das Faktorisieren großer Zahlen, auf dem RSA beruht, liegt zwar in NP, gilt aber nicht als NP-vollständig – es könnte leichter sein als SAT. Quantencomputer könnten es mit Shors Algorithmus effizient lösen; für NP-vollständige Probleme ist dagegen kein solcher Durchbruch bekannt.

Für Entwickler übersetzt

Mit SAT4J gibt es einen ausgereiften SAT-Solver in reinem Java – er steckt unter anderem in Eclipse, wo er die Abhängigkeiten von Plugins auflöst. Variablen sind Zahlen ab 1, eine negative Zahl bedeutet „nicht“:

// (A ∨ ¬B) ∧ (B ∨ C) ∧ (¬A ∨ ¬C)  – A=1, B=2, C=3
ISolver solver = SolverFactory.newDefault();
solver.newVar(3);
solver.addClause(new VecInt(new int[] { 1, -2 }));
solver.addClause(new VecInt(new int[] { 2,  3 }));
solver.addClause(new VecInt(new int[] { -1, -3 }));

if (solver.isSatisfiable()) {
    int[] belegung = solver.model();   // z. B. [1, 2, -3]: A wahr, B wahr, C falsch
}
// Ausnahmen (ContradictionException, TimeoutException) hier weggelassen

// Kartenfärbung: Variable für "Land l hat Farbe f"
int var(int land, int farbe) { return land * FARBEN + farbe + 1; }
for (int[] kante : nachbarn)
    for (int f = 0; f < FARBEN; f++)
        solver.addClause(new VecInt(new int[] { -var(kante[0], f), -var(kante[1], f) }));

Die praktische Lehre: Wer merkt, dass sein Problem NP-vollständig ist, schreibt keinen eigenen Suchalgorithmus, sondern übersetzt es für einen Solver – und setzt ein Zeitlimit, denn eine Garantie gibt es nicht.

Häufige Irrtümer

Verwandte Begriffe