Editing Log-space reduction (section)

== Logspace computable function ==
{{Anchor|Log-space computable function}}

A function <math>f: 2^* \to 2^*</math> is '''(implicitly) logspace computable''' iff:<ref name="AB88">{{cite book |last1=Arora |first1=Sanjeev |title=Computational complexity. A modern approach |last2=Barak |first2=Boaz |publisher=[[Cambridge University Press]] |year=2009 |isbn=978-0-521-42426-4 |zbl=1193.68112 |authorlink1=Sanjeev Arora |author2link=Boaz Barak}}</ref>{{Pg|page=88}}

* Its output length is polynomially bounded: There exists some <math>c > 0</math> such that <math>f(x) \leq |x|^c</math> for all <math>x\in 2^* </math>.
* <math>L_f=\left\{\langle x, i\rangle \mid f(x)_i=1\right\}</math> is in complexity class L.
* <math>L_f^{\prime}=\{\langle x, i\rangle|i \leq|f(x)|\}</math> is in complexity class L.

Intuitively, the first condition states that the function creates outputs that are short enough, such that creating a single pointer on the output will take only logspace. That condition is necessary in order for pointers on the output to exist at all.

The second condition states that any ''particular'' output location is computable in logspace.

The third condition states that checking if a pointer is a valid pointer is decidable in logspace.

{{Anchor|Log-space transducer}}Equivalently, A function <math>f: 2^* \to 2^*</math> is logspace computable iff it is computed by a Turing machine with a log-length work tape, that halts on any input, and an output tape that is write-only and write-once, meaning that at each step, the machine may either write nothing, or write a bit and move the write-head forward by one.<ref name="AB88" />{{Pg|page=94}} Such a machine is usually called a '''logspace [[Finite-state transducer|transducer]]'''. Note that such a machine, if it halts, must halt in polynomial steps, since its work tape has log-length. Therefore its output length is polynomially bounded.

One intuition is that such a function can be computed by a program that can only keep a constant number of pointers to the input, and a constant number of counters that can only contain integers of size <math>\mathsf{poly}(n)</math>. This is because a [[counter machine]] with a constant number of counters that count up to <math>f(n)</math> is equivalent to a Turing machine with space complexity <math>O(\log f(n))</math>.<ref>{{cite book |last1=Meyer |first1=Albert R. |url=http://euro.ecom.cmu.edu/people/faculty/mshamos/1977Meyer.pdf |title=Perspectives on Computer Science: From the 10th Anniversary Symposium at the Computer Science Department, Carnegie-Mellon University |last2=Shamos |first2=Michael Ian |date=1977 |publisher=Academic Press |editor-last=Jones |editor-first=Anita K. |location=New York |pages=125–146 |chapter=Time and space}}</ref>

=== Closure ===
The most important property of logspace computability is that, if functions <math>f, g</math> are logspace computable, then so is their [[Function composition|composition]] <math>g \circ f</math>. This allows the concept of logspace reduction to be transitive.

Given two logspace transducers, their composition is still a logspace transducer: feed the output from one transducer (A→B) to another (B→C). At first glance, this seems incorrect because intuitively, the A→C transducer needs to store the output tape from the A→B transducer onto the work tape, in order to feed it into the B→C reducer, but this is not necessary, by the following construction.

Define the A→C transducer as follows: It simulates the operations of B→C transducer. Every time the B→C transducer needs to make a read, the A→C transducer re-run the A→B transducer to re-compute only the exact output bit that is needed, and so only one bit of the output of the A→B transducer needs to be stored at any moment.