Log-space reduction

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, a log-space reduction is a <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a> computable by a <a href="/facts/Deterministic_Turing_machine/ojCtglYu">deterministic Turing machine</a> using <a href="/facts/Logarithmic_space/vCMV0edS">logarithmic space</a>. Conceptually, this means it can keep a constant number of <a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointers</a> into the input, along with a logarithmic number of fixed-size <a href="/facts/Integer/PUwwrawx">integers</a>. It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space. Formally, this reduction is executed via a <a href="/facts/Log-space_transducer/83JWq3k7">log-space transducer</a>.
Such a machine has polynomially-many configurations, so log-space reductions are also <a href="/facts/Polynomial-time_reduction/bBvfFxyM">polynomial-time reductions</a>. However, log-space reductions are probably weaker than polynomial-time reductions; while any non-empty, non-full language in <a href="/facts/P_(complexity)/2TYvck4k">P</a> is polynomial-time reducible to any other non-empty, non-full language in P, a log-space reduction from an <a href="/facts/NL_(complexity)/FvNaeSaM">NL</a>-complete language to a language in <a href="/facts/L_(complexity)/vCMV0edS">L</a>, both of which would be languages in P, would imply the unlikely L = NL. It is an open question if the <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problems are different with respect to log-space and polynomial-time reductions.
Log-space reductions are normally used on languages in P, in which case it usually does not matter whether <a href="/facts/Many-one_reduction/YUKNlYPh">many-one reductions</a> or <a href="/facts/Turing_reduction/qczcQTbz">Turing reductions</a> are used, since it has been verified that L, <a href="/facts/SL_(complexity)/NHcut8wL">SL</a>, 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 classes. However, other subclasses of P such as <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a> 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 non-empty, non-full problem in L is trivially L-<a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> under log-space 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 <a href="/facts/SL_(complexity)/NHcut8wL">SL</a> for a list of some SL-complete problems that can now be used as subroutines in log-space reductions.

Log-space reduction open-in-new

Log-space reduction