NSPACE

NSPACE (seldom NTAPE, from English: Non-deterministic Turing machine tape) is a term from complexity theory , a branch of theoretical computer science .

There NSPACE (f) stands for the space complexity class of the decision problems that can be solved by a nondeterministic Turing machine with space requirements O (f). It is the nondeterministic counterpart to DSPACE . NSPACE (f (n)) is closed against complement ( theorem of Immerman and Szelepcsényi ).

Other complexity classes are often defined with NSPACE. So NPSPACE can be derived from NSPACE as follows:

${\displaystyle {\mbox{NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}$

Web links

• NSPACE . In: Complexity Zoo. (English)