from Wikipedia, the free encyclopedia

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)