Polynomialzeitreduktion
Eine Polynomialzeitreduktion (auch als polynomielle Reduktion bezeichnet) ist eine spezielle Form der Reduktion.
Neben der Forderung, dass eine Sprache L' auf
eine andere Sprache L 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.