Suvarna Garge (Editor)

Log space computable function

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

A log-space computable function is a function f : Σ ∗ → Σ ∗ 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.

Contents

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.

    • References

    Log-space computable function Wikipedia
    (Text) CC BY-SA