Log-space reduction
From Wikipedia, the free encyclopedia
 |
This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (April 2009) |
|
|
This article may not meet the general notability guideline. Please help to establish notability by adding reliable, secondary sources about the topic. If notability cannot be established, the article is likely to be merged or deleted. (April 2009) |
In 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 pointers 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 non-empty, non-full language in P is polynomial-time reducible to any other non-empty, non-full 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 classes. 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, almost[1] 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 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.
- ^ I say "almost" because there is one problem (and its complement) which no other problems can be many-one reduced to (although they can be Turing reduced to): the problem that accepts everything (and the one that rejects everything).
[edit] Further reading
- Christos Papadimitriou (1994). "Chapter 8: Reductions And Completeness". Computational Complexity (1st edition ed.). Addison Wesley. pp. 159–180. ISBN 0-201-53082-1.
