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:
Web links
- NSPACE . In: Complexity Zoo. (English)