Begriff aus der Komplexitätstheorie.

Eine Sprache L₁ (bzw. ein Entscheidungsproblem) ist auf eine Sprache L₂ Logspace-reduzierbar, Notation L₁ ≤_logL₂, wenn es eine von einer Turing-Maschine mit ⌈ld(n)⌉ Zellen auf dem Arbeitsband 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: \begin{eqnarray}w\in {L}_{1}\iff f(w)\in {L}_{2}.\end{eqnarray}

Logspace-Reduktionen spielen für die Raumkomplexität diejenige Rolle, die polynomielle Zeitreduktionen in der Theorie der NP-Vollständigkeit spielen.