Reduktion (genauer: polynomiale Reduktion) ist eine der wichtigsten Techniken der Theoretischen Informatik. Man zeigt damit, dass ein Problem mindestens so schwer ist wie ein anderes: Man transformiert Instanzen des Problems A in Instanzen von Problem B, sodass eine Lösung von B eine Lösung von A liefert. So vergleicht man Probleme, ohne sie direkt zu lösen.
Grundidee
Eine Reduktion A ≤ B bedeutet: Gibt es einen Algorithmus für B, dann gibt es auch einen für A – man übersetzt die Eingabe, ruft den B-Algorithmus auf und übersetzt das Ergebnis zurück. Damit ist B „mindestens so schwer" wie A. Die Übersetzung muss dabei in Polynomzeit laufen (gemessen in Big-O-Notation), sonst verliert man den Komplexitäts-Bezug.
Eigenschaften
- Transitivität: Aus A ≤ B und B ≤ C folgt A ≤ C – Reduktionen lassen sich hintereinanderschalten.
- Klasse-Erhalt: Ist A ≤ B und B in P, dann ist auch A in P.
- Kontraposition: Ist A ≤ B und A ist nicht in P, dann ist auch B nicht in P – so weist man Untergrenzen nach.
Reduktion in der NP-Theorie
Die Reduktion ist das Schlüsselwerkzeug der NP-Vollständigkeit: Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes NP-Problem auf es reduzierbar ist. Den Ausgangspunkt lieferte das Cook-Levin-Theorem mit dem Satisfiability-Problem (SAT); von dort aus reduziert man SAT auf weitere Probleme. Ein klassisches Beispiel: der Hamilton-Pfad lässt sich auf das Rundreiseproblem (TSP) reduzieren, 3-SAT auf das Cliquen-Problem. Praktisch nutzt man Reduktionen auch, um Optimierungsprobleme auf bekannte Lösungsverfahren abzubilden – oder um zu zeigen, dass für hartnäckige Fälle nur Heuristiken bleiben. Grundlage jeder Reduktion ist die Aussagenlogik; ob die so beweisbaren Schranken prinzipiell überwindbar sind, fragt das P-vs-NP-Problem. Siehe auch: Algorithmus.