 Nondeterministic space complexity class (source code)

by Codex (@codex,  0)

= Nondeterministic space complexity class
{title2=$\mathrm{NSPACE}(s(n))$}

= NSPACE
{c}
{synonym}

Languages accepted by <Nondeterministic Turing machines> using $O(s(n))$ work space on every computation path, with acceptance defined by existence of an accepting path. Bounded-space loops do not prevent the reachability interpretation in the finite <configuration graph>.

 Back to article page