Begriff aus der Komplexitätstheorie.

Eine Sprache L₁ bzw. ein Entscheidungsproblem ist auf eine Sprache L₂ in polynomieller Zeit reduzierbar, Notation L₁ ≤_pL₂, wenn es eine in polynomieller Zeit berechenbare Transformation f gibt, die Wörter über dem Alphabet von L₁ in Wörter über dem Alphabet von L₂ so überführt, daß gilt: w ∈ L₁ ⇔ f(w) ∈ L₂. Aus L₂ ∈ P (P (Komplexitätsklasse)) und L₁ ≤_pL₂ folgt, daß L₁ ∈ P ist.

Polynomielle Zeitreduktionen bilden die Grundlage der Theorie der NP-Vollständigkeit.