Log-space computable function explained

In computational complexity theory, a log-space computable function is a function

f\colon\Sigma^\ast → \Sigma^\ast

that requires only

O(logn)

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]

References

Sipser, Michael (2006), Introduction to the Theory of Computation, Cengage Learning, .

Notes and References

Sipser (2006) International Second Edition, p. 328.