Reduktionen sind Methoden der theoretischen Informatik, mit denen die Komplexität von Problemen oder Sprachen verglichen werden können.

Polynomialzeit-Reduktionen (auch als polynomielle Reduktionen bezeichnet) sind eine spezielle Form von Reduktionen.

Eine Sprache ist auf eine Sprache reduzierbar, wenn sich über eine Funktion jedes Wort der Sprache in ein Wort der Sprache bijektiv abbilden lässt.

Formal ausgedrückt:

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

So lässt sich beispielsweise die Sprache aller Quadratzahlen

auf die Sprache aller Multiplikationen mit 2 Faktoren

reduzieren, da über die Abbildung jedes Wort aus in ein Wort aus abgebildet werden kann und jedes Bild dieser Funktion wiederum ein Urbild in 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 geschrieben.

Neben der Forderung, dass eine Sprache auf eine andere Sprache mittels einer Funktion reduzierbar ist, muss diese Funktion für eine polynomielle Reduktion zusätzlich in Polynomialzeit berechnet werden können.

Polynomielle Reduktionen werden in der Komplexitätstheorie üblicherweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NP auch NP-vollständig ist.

Als Schreibweise wird hierbei häufig verwendet.