Log-space computable function
From HandWiki
In computational complexity theory, a log-space computable function is a function [math]\displaystyle{ f\colon \Sigma^\ast \rightarrow \Sigma^\ast }[/math] that requires only [math]\displaystyle{ O(\log n) }[/math] memory to be computed (this restriction does not apply to the size of the output). The computation is generally done by means of a log-space transducer.
Log-space reductions
The main use for log-space computable functions is in log-space reductions. This is a means of transforming an instance of one problem into an instance of another problem, using only logarithmic space.
Examples of log-space computable functions
- Function converting a problem of a non-deterministic Turing machine that decides a language A in log-space to ST-connectivity.[1]
Notes
- ↑ Sipser (2006) International Second Edition, p. 328.
References
- Sipser, Michael (2006), Introduction to the Theory of Computation, Cengage Learning, ISBN:978-0-619-21764-8.
 |  |
