Editing Log-space reduction (section)

== Logspace reduction ==
A language <math>L</math> is '''logspace (many-one) reducible''' to another language <math>L'</math>, notated as <math>L \leq_{l} L'</math>, iff there exists an implicitly logspace computable function <math>f</math> such that <math>x \in L \iff f(x) \in L'</math>. This is a transitive relation, because logspace computability is closed under composition, as previously shown.

A language <math>L</math> is '''NL-complete''' iff it is NL, and any language in NL is logspace reducible to it.

Most naturally-occurring polynomial-time reductions in complexity theory are logspace reductions. In particular, this is true for the standard proof showing that the [[Boolean satisfiability problem|SAT problem]] is [[NP-completeness|NP-complete]], and that the [[Circuit Value Problem|circuit value problem]] is [[P-complete]]. This is also often the case for showing that the [[True quantified Boolean formula]] problem is [[PSPACE-complete]]. This is because the need for memory in such reduction constructions is for counting up to <math>p(n)</math> for some polynomial <math>p</math> in the input length <math>n</math>, and this can be done in logarithmic space.<ref>{{cite book |last1=Garey |first1=Michael R. |title=Computers and Intractability: A Guide to the Theory of NP-Completeness |last2=Johnson |first2=David S. |date=1979 |publisher=W. H. Freeman |isbn=978-0-7167-1045-5|location=New York |oclc=4195125}}</ref>{{Pg|page=180}}

While logspace many-one reduction implies polynomial time many-one reduction, it is unknown whether this is an equivalence, or whether there are problems that are NP-complete under polynomial time reduction, but not under logspace reduction. Any solution to this problem would solve this problem: Are deterministic [[Linear bounded automaton|linear bounded automata]] equivalent to nondeterministic linear bounded automata?<ref>{{Cite journal |last=Lind |first=John |last2=Meyer |first2=Albert R. |date=1973-07-01 |title=A characterization of log-space computable functions |url=https://dl.acm.org/doi/10.1145/1008293.1008295 |journal=SIGACT News |volume=5 |issue=3 |pages=26–29 |doi=10.1145/1008293.1008295 |issn=0163-5700}}</ref>