Reduktion (theoretische Informatik)

Die Reduktion ist eine Methode der theoretischen Informatik, mit der die Komplexität von Problemen oder Sprachen durch Umformung eines Problems in ein anderes verglichen werden kann.

Eine Sprache $L'$ ist auf eine Sprache $L$ reduzierbar, wenn sich über eine Funktion $f\;$ jedes Wort der Sprache $L'$ in ein Wort der Sprache $L$ bijektiv abbilden lässt.

Formal ausgedrückt: $w\in L'\iff f(w)\in L$

Zusätzlich ist gefordert, dass sich diese Funktion auf deterministischem Wege berechnen lässt.

So lässt sich beispielsweise die Sprache aller Quadratzahlen

$L_{Q}:=\left\{a\in \mathbb {Z} \colon b=a^{2}\right\}$

auf die Sprache aller Multiplikationen mit 2 Faktoren

$L_{M}:=\left\{(a_{1},a_{2})\in \mathbb {Z} ^{2}\colon b=a_{1}\cdot a_{2}\right\}$

reduzieren, da über die Abbildung $f\colon \mathbb {Z} \to \mathbb {Z} ^{2},\,a\mapsto (a,a)$ jedes Wort aus $L_{Q}$ in ein Wort aus $L_{M}$ abgebildet werden kann und jedes Bild dieser Funktion $f\;$ wiederum ein Urbild in $L_{Q}$ besitzt.

Mit dieser Reduktion ist gezeigt, dass ein Algorithmus, welcher zwei natürliche Zahlen miteinander multipliziert, auch eine natürliche Zahl quadrieren kann, das Quadrieren also ein „höchstens so schweres “ Problem wie das Multiplizieren ist.

Formal wird hierfür $L_{Q}\leq L_{M}$ geschrieben.

Oft spielt auch die Zeit oder der Speicherplatz eine Rolle, die bzw. der zum Berechnen der Reduktion gebraucht wird, siehe hierzu unter Anderem: Polynomialzeit-Reduktion.