In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space.
Formally, this reduction is executed via a log-space transducer.
It is an open question if the NP-complete problems are different with respect to log-space and polynomial-time reductions.
While even weaker reductions exist, they are not often used in practice, because complexity classes smaller than L (that is, strictly contained or thought to be strictly contained in L) receive relatively little attention.
The tools available to designers of log-space reductions have been greatly expanded by the result that L = SL; see SL for a list of some SL-complete problems that can now be used as subroutines in log-space reductions.