Log-space computable function

A log-space computable function is a function $f\colon \Sigma ^{\ast }\rightarrow \Sigma ^{\ast }$ that requires only $O(\log n)$ 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.

gollark: (Minus overhead)

gollark: The HDD isn't throttled by it.

gollark: USB 2 goes to 480Mbps. This is 60MB/s.

gollark: Which is something like a twentieth of a decent HDD's write speed.

gollark: My USB 3 one can manage an *impressive* 5MB/s or so.

References

Sipser, Michael (2006), Introduction to the Theory of Computation, Cengage Learning, ISBN 978-0-619-21764-8.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Sipser (2006) International Second Edition, p. 328.