In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.
The measure DSPACE is used to define complexity classes, sets of all of the decision problems that 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 that can be solved by a deterministic Turing machine using space O(f(n)).
Several important complexity classes are defined in terms of DSPACE.
, where c is a constant depending on M. Let S denote the set of all possible crossing sequences of M on x.
: if it is longer than that, then some configuration will repeat, and M will go into an infinite loop.
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.
This is solved by defining the multi-tape 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.
Since many symbols might be packed into one by taking a suitable power of the alphabet, for all c ≥ 1 and f such that f(n) ≥ 1, the class of languages recognizable in c f(n) space is the same as the class of languages recognizable in f(n) space.
This justifies usage of big O notation in the definition.
The space hierarchy theorem shows that, for every space-constructible function
DSPACE is the deterministic counterpart of NSPACE, the class of memory space on a non-deterministic Turing machine.
By Savitch's theorem,[3] we have that NTIME is related to DSPACE in the following way.