DSPACE

For digital repositories, see 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 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.

Complexity classes

The measure DSPACE is used to define complexity classes, sets of all of the decision problems 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 problems 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:

• REG = DSPACE(O(1)), where REG is the class of regular languages. In fact, REG = DSPACE(o(log log n)) (that is, Ω(log log n) space is required to recognize any nonregular language).
• L = DSPACE(O(log n))
• PSPACE = $\bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(n^k)$
• EXPSPACE = $\bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})$

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 L (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 theorem shows that, for every space-constructible function $f: \mathbb{N} \to \mathbb{N}$, there exists some language L which is decidable in space O(f(n)) but not in space o(f(n)). See space hierarchy theorem for details.

Relation with other complexity classes

DSPACE is the deterministic counterpart of NSPACE, the class of memory space on a nondeterministic Turing machine. By Savitch's theorem, we have that

$\mbox{DSPACE}[s(n)] \subseteq \mbox{NSPACE}[s(n)] \subseteq \mbox{DSPACE}[(s(n))^2].$

NTIME is related to DSPACE in the following way. For any time constructible function t(n), we have

$\mbox{NTIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))$.

References

Complexity Zoo: DSPACE(f(n)).