NSPACE
Encyclopedia
In computational complexity theory
, the complexity class
NSPACE(f(n)) is the set of decision problem
s that can be solved by a non-deterministic Turing machine
using space O(f(n)), and unlimited time. It is the non-deterministic counterpart of DSPACE
.
Several important complexity classes can be defined in terms of NSPACE. These include:
The last two results above follow from Savitch's theorem
, which states that for any function f(n) ≥ log(n),
The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function
NSPACE can be related to DTIME
as follows. For any space constructible function s(n),
A futher generalization is ASPACE, defined with alternating Turing machines.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NSPACE(f(n)) is the set of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that can be solved by a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
using space O(f(n)), and unlimited time. It is the non-deterministic counterpart of DSPACE
DSPACE
In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
.
Several important complexity classes can be defined in terms of NSPACE. These include:
- REGRegular languageIn theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
= DSPACE(O(1)) = NSPACE(O(1)), where REG is the class of regular languageRegular languageIn theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s (nondeterminism does not add power in constant space). - NLNL (complexity)In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
= NSPACE(O(log n)) - CSLContext-sensitive languageIn theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
= NSPACE(O(n)), where CSL is the class of context-sensitive languageContext-sensitive languageIn theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
s. - PSPACEPSPACEIn computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
= NPSPACE =
- EXPSPACEEXPSPACEIn complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
= NEXPSPACE =
The last two results above follow from Savitch's theorem
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
, which states that for any function f(n) ≥ log(n),
- NSPACE(f(n)) ⊆ DSPACE(f2(n)).
The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function
NSPACE can be related to DTIME
DTIME
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
as follows. For any space constructible function s(n),
A futher generalization is ASPACE, defined with alternating Turing machines.