Log-space computable function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

Notes[edit]

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

References[edit]