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.