Direkt zum Inhalt

Lexikon der Mathematik: Reduktion

algorithmische Technik beim Topdown Entwurf von Algorithmen.

Eine Reduktion des Problems P1 auf das Problem P2 ist ein Algorithmus A1/P2, der das Problem P1 unter der Voraussetzung effizient löst, daß eine Black Box mit konstanten Kosten zur Lösung von P2 benutzt werden darf. AUS A1/P2 ergibt sich ein effizienter Algorithmus A1 für P1, wenn die Black Box durch einen effizienten Algorithmus für P2 ersetzt werden kann. In der Komplexitätstheorie werden Reduktionen benutzt, um aus der Schwierigkeit, P1 zu lösen, auf die Schwierigkeit, P2 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 NC1-Reduktion.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos