Home > Log-space reduction

Log-space reductions are probably weaker than polynomial-time reductions; while any language in P is polynomially reducible to any other language in P, a log-space reduction between a language in NL and a language in L, both subsets of P, would imply the unlikely L = NL.

Log-space reductions are normally used on languages in P, in which case it usually does not matter whether many-one reductions or Turing reductions are used, since it has been verified that L, SL, NL, and P are all closed under Turing reductions, meaning that Turing reductions can be used to show a problem is in any of these languages. However, other subclasses of P such as NC may not be closed under Turing reductions, and so many-one reductions must be used.

Just as polynomial-time reductions are useless within P and its subclasses, log-space reductions are useless to distinguish problems in L and its subclasses; in particular, every problem in L is trivially L-complete under log-space reductions. While even weaker reductions exist, they are not often used in practice, because languages smaller than 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.