This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "DSPACE" – news ·newspapers ·books ·scholar ·JSTOR(October 2009) (Learn how and when to remove this message)

Incomputational complexity theory,DSPACE orSPACE is thecomputational resource describing the resource ofmemory space for adeterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a givencomputational problem with a givenalgorithm.

The measureDSPACE is used to definecomplexity classes, sets of all of thedecision problems that can be solved using a certain amount of memory space. For each functionf(n), there is acomplexity class SPACE(f(n)), the set ofdecision problems that can be solved by adeterministic Turing machine using spaceO(f(n)). There is no restriction on the amount ofcomputation time that can be used, though there may be restrictions on some other complexity measures (likealternation).

Several important complexity classes are defined in terms ofDSPACE. These include:

• REG = DSPACE(O(1)), whereREG is the class ofregular languages. In fact, REG = DSPACE(o(log log n)) (that is,Ω(log log n) space is required to recognize any non-regular language).^[1][2]

Proof:Suppose that there exists a non-regular languageL ∈ DSPACE(s(n)), fors(n) =o(log logn). LetM be aTuring machine decidingL in spaces(n). By our assumptionL ∉ DSPACE(O(1)); thus, for any arbitrary${\displaystyle k\in \mathbb{N}}$, there exists an input ofM requiring more space thank.

Letx be an input of smallest size, denoted by n, that requires more space thank, and${\displaystyle \mathcal{C}}$ be the set of allconfigurations ofM on inputx. BecauseM ∈ DSPACE(s(n)), then${\displaystyle |\mathcal{C}|\le 2^{c\cdot s(n)}=o(\log n)}$, wherec is a constant depending onM.

LetS denote the set of all possiblecrossing sequences ofM onx. Note that the length of a crossing sequence ofM onx is at most${\displaystyle |\mathcal{C}|}$: if it is longer than that, then some configuration will repeat, andM will go into an infinite loop. There are also at most${\displaystyle |\mathcal{C}|}$ possibilities for every element of a crossing sequence, so the number of different crossing sequences ofM onx is

According topigeonhole principle, there exist indexesi <j such that${\displaystyle {\mathcal{C}}_i(x)={\mathcal{C}}_j(x)}$, where${\displaystyle {\mathcal{C}}_i(x)}$ and${\displaystyle {\mathcal{C}}_j(x)}$ are the crossing sequences at boundaryi andj, respectively.

Letx' be the string obtained fromx by removing all cells fromi + 1 toj. The machineM still behaves exactly the same way on inputx' as on inputx, so it needs the same space to computex' as to computex. However,|x'| < |x|, contradicting the definition ofx. Hence, there does not exist such a languageL as assumed. □

The above theorem implies the necessity of thespace-constructible function assumption in thespace hierarchy theorem.

• L = DSPACE(O(log n))
• PSPACE =${\displaystyle \bigcup _{k\in \mathbb{N}}\mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(n^k)}$
• EXPSPACE =${\displaystyle \bigcup _{k\in \mathbb{N}}\mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(2^{n^k})}$

DSPACE is traditionally measured on adeterministic Turing machine. Several important space complexity classes aresublinear, 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 themulti-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. This allows smaller space classes, such asL (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).

Since many symbols might be packed into one by taking a suitable power of the alphabet, for allc ≥ 1 andf such thatf(n) ≥1, the class of languages recognizable incf(n) space is the same as the class of languages recognizable inf(n) space. This justifies usage ofbig O notation in the definition.

Thespace hierarchy theorem shows that, for everyspace-constructible function${\displaystyle f:\mathbb{N}\to \mathbb{N}}$, there exists some languageL that is decidable in space${\displaystyle O(f(n))}$ but not in space${\displaystyle o(f(n))}$.

DSPACE is the deterministic counterpart ofNSPACE, the class ofmemory space on anon-deterministic Turing machine. BySavitch's theorem,^[3] we have that

${\displaystyle \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(s(n))\subseteq \mathsf{N}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(s(n))\subseteq \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}((s(n){)}^2).}$

NTIME is related to DSPACE in the following way. For anytime constructible functiont(n), we have

${\displaystyle \mathsf{N}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(t(n))\subseteq \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(t(n))}$.

A much better simulation is known fordeterministic time: if${\displaystyle t(n)\ge n}$,

${\displaystyle \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(t(n))\subseteq \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}\left(\sqrt{t(n)\log t(n)}\right)}$

by a result ofWilliams,^[4] improving an older bound of${\displaystyle O(t/\log t)}$ byHopcroft, Paul, andValiant.^[5]

On the other hand, for any function${\displaystyle s(n)\ge \log n}$,

${\displaystyle \mathsf{D}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(s(n))\subseteq \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(2^{O(s(n))})}$.

• Szepietowski, Andrzej (1994).Turing Machines with Sublogarithmic Space.Springer Science+Business Media.ISBN 978-3-540-58355-4.
• Arora, Sanjeev;Barak, Boaz (2009).Computational complexity. A modern approach.Cambridge University Press.ISBN 978-0-521-42426-4.Zbl 1193.68112.

• Complexity Zoo:DSPACE(f(n)).

• Computational resources
• Complexity classes

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from October 2009
• All articles needing additional references