|
|
|
|
|
Log-space ReductionIn computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of points into the input, along with a logarithmic number of fixed-size integers. Since such a machine has polynomially-many configurations, log-space reductions are also polynomial-time reductions. 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. It is an open question if the NP-complete 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 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.
|
 |
| |
|
|