Log-space computable function


A log-space computable function is a function that requires only memory to be computed. 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