algorithmische Technik beim Topdown Entwurf von Algorithmen.

Eine Reduktion des Problems P₁ auf das Problem P₂ ist ein Algorithmus A₁/P₂, der das Problem P₁ unter der Voraussetzung effizient löst, daß eine Black Box mit konstanten Kosten zur Lösung von P₂ benutzt werden darf. AUS A₁/P₂ ergibt sich ein effizienter Algorithmus A₁ für P₁, wenn die Black Box durch einen effizienten Algorithmus für P₂ ersetzt werden kann. In der Komplexitätstheorie werden Reduktionen benutzt, um aus der Schwierigkeit, P₁ zu lösen, auf die Schwierigkeit, P₂ zu lösen, zu schließen. Bezogen auf die betrachtete Komplexitätsklasse muß ein passender Reduktionstyp gewählt werden, z. B. polynomielle Zeitreduktion, Turing-Reduktion, Logspace-Reduktion oder NC¹-Reduktion.