Reduktion (theoretische Informatik)

Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird. Gibt es einen Algorithmus für das zweite Problem, so lässt sich über die Reduktion auch das erste lösen. Die Reduzierbarkeit ist daher eine Relation auf der Menge der Probleme, durch welche die Berechenbarkeit oder die Komplexität zweier Probleme zueinander in Bezug gesetzt werden kann.

Der Grundgedanke, Reduktionen für die Untersuchung von Problemen zu verwenden, geht auf einen Aufsatz des Mathematikers Emil Post aus dem Jahr 1944 zurück.^[1]

Es werden verschiedene Arten von Reduktionen unterschieden. Die häufigsten sind dabei die One-one- oder Many-one-Reduktion, sowie die Truth-table- und Turing-Reduktion (letztere nach Alan Turing benannt). Jede von ihnen enthält jeweils die vorangegangenen als Sonderfall.

Während in der Berechenbarkeitstheorie meist der Nachweis des Vorhandenseins einer bestimmten Reduktion zwischen zwei Problemen genügt, werden in der Komplexitätstheorie zusätzliche Anforderungen an den Ressourcenverbrauch der Reduktion gestellt. Gewöhnliche Ressourcen sind hierbei Zeit oder Speicherplatz. Dies führt auf die Begriffe der Karp- (nach Richard M. Karp) und Cook-Reduktion (nach Stephen Cook).

1. ↑ Emil Post: Recursively enumerable sets of positive integers and their decision problems. In: Bulletin of the American Mathematical Society. Band 50, Nr. 5, 1944, S. 284–316 (englisch, ams.org [PDF; 4,0 MB]).