DSPACE
Encyclopedia
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 given algorithm
. It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory
needed to run a given program.
es, sets of all of the decision problem
s which can be solved using a certain amount of memory space. For each function f(n), there is a complexity class
SPACE(f(n)), the set of decision problem
s which can be solved by a deterministic Turing machine using space O(f(n)). There is no restriction on the amount of computation time which can be used, though there may be restrictions on some other complexity measures (like alternation).
Several important complexity classes are defined in terms of DSPACE. These include:
(logarithmic space), to be defined in terms of the amount of space used by all of the work tapes (excluding the special input and output tapes).
shows that, for every space-constructible function
, there exists some language L which is decidable in space 
but not in space 
. See space hierarchy theorem
for details.
, the class of memory space on a nondeterministic Turing machine. By Savitch's theorem
, we have that
NTIME
is related to DSPACE in the following way. For any time constructible function t(n), we have
.
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...
, DSPACE or SPACE is the computational resource
Computational resource
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....
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
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
with a given algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
. It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
needed to run a given program.
Complexity classes
The measure DSPACE is used to define complexity classComplexity 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:...
es, sets of all of the 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 which can be solved using a certain amount of memory space. For each function f(n), there is a 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:...
SPACE(f(n)), 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 which can be solved by a deterministic Turing machine using space O(f(n)). There is no restriction on the amount of computation time which can be used, though there may be restrictions on some other complexity measures (like alternation).
Several important complexity classes are defined in terms of DSPACE. 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)), 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. In fact, REG = DSPACE(o(log log n)) (that is, Ω(log log n) space is required to recognize any nonregular language). - LL (complexity)In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
= DSPACE(O(log n)) - 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 :...
=
- 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...
=
Machine models
DSPACE is traditionally measured on a deterministic Turing machine. Several important space complexity classes are sublinear, that is, smaller than the size of the input. Thus, "charging" the algorithm for the size of the input, or for the size of the output, would not truly capture the memory space used. This is solved by defining the multi-string Turing machine with input and output, which is a standard multi-tape Turing machine, except that the input tape may never be written-to, and the output tape may never be read from. This allows smaller space classes, such as LL (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
(logarithmic space), to be defined in terms of the amount of space used by all of the work tapes (excluding the special input and output tapes).
Hierarchy Theorem
The space hierarchy theoremSpace hierarchy theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
shows that, for every space-constructible function
, there exists some language L which is decidable in space but not in space . See space hierarchy theoremSpace hierarchy theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
for details.
Relation with other complexity classes
DSPACE is the deterministic counterpart of NSPACENSPACE
In computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...
, the class of memory space on a nondeterministic Turing machine. By 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,...
, we have that
NTIME
NTIME
In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
is related to DSPACE in the following way. For any time constructible function t(n), we have
.