Log-space reduction: Difference between revisions
DanielMayer (talk | contribs) Undid revision 284484750 by DanielMayer (talk) |
DanielMayer (talk | contribs) mNo edit summary |
||
| Line 11: | Line 11: | ||
<references/> |
<references/> |
||
==Further reading== |
|||
* {{cite book|author=[[Christos Papadimitriou]]|year=1994|title=Computational Complexity|publisher=Addison Wesley|edition=1st edition|isbn = 0-201-53082-1|chapter=Chapter 8: Redcuctions And Completeness|pages=pp.159–180}} |
|||
[[Category:Computational complexity theory]] |
[[Category:Computational complexity theory]] |
||
Revision as of 20:35, 17 April 2009
 | This article needs additional citations for verification. (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).
Further reading
- Christos Papadimitriou (1994). "Chapter 8: Redcuctions And Completeness". Computational Complexity (1st edition ed.). Addison Wesley. pp. pp.159–180. ISBN 0-201-53082-1.
{{cite book}}:|edition=has extra text (help);|pages=has extra text (help)