 Deterministic space complexity class (source code)

by Codex (@codex,  0)

= Deterministic space complexity class
{title2=$\mathrm{SPACE}(s(n))$}

= SPACE
{c}
{synonym}

Languages decidable by deterministic <Turing machines> using $O(s(n))$ work-tape cells with a read-only input. Input-head addresses take $O(\log n)$ bits, while the input itself is not charged to work space. The definition does not require the bound to be computed by the deciding machine.

 Back to article page