Editing DSPACE (section)

==Complexity classes==

The measure '''DSPACE''' is used to define [[complexity class]]es, sets of all of the [[decision problem]]s 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 problem]]s that can be solved by a [[deterministic Turing machine]] using space ''O''(''f''(''n'')).  There is no restriction on the amount of [[computation time]] that can be used, though there may be restrictions on some other complexity measures (like [[Alternation (complexity)|alternation]]).

Several important complexity classes are defined in terms of '''DSPACE'''. These include:

* [[regular language|REG]] = DSPACE(''O''(1)), where '''REG''' is the class of [[regular language]]s. In fact, REG = DSPACE(''o''(log&nbsp;log&nbsp;''n'')) (that is, {{math|Ω(log&nbsp;log&nbsp;''n'')}} space is required to recognize any non-regular language).<ref name=AS28>Szepietowski (1994) p. 28</ref><ref>{{citation |last1=Alberts|first1=Maris|title=Space complexity of alternating Turing machines|year=1985}}</ref>

''Proof:''
Suppose that there exists a non-regular language ''L'' ∈ DSPACE(''s''(''n'')), for ''s''(''n'') = ''o''(log log ''n''). Let ''M'' be a [[Turing machine]] deciding ''L'' in space ''s''(''n''). By our assumption ''L'' ∉ DSPACE(''O''(1)); thus, for any arbitrary <math>k \in \mathbb{N}</math>, there exists an input of ''M'' requiring more space than ''k''.

Let ''x'' be an input of smallest size, denoted by n, that requires more space than ''k'', and <math>\mathcal{C}</math> be the set of all [[Turing machine|configurations]] of ''M'' on input ''x''. Because ''M'' ∈ DSPACE(''s''(''n'')), then <math>|\mathcal{C}| \le 2^{c.s(n)} = o(\log n)</math>, where ''c'' is a constant depending on ''M''.

Let ''S'' denote the set of all possible [[Crossing sequence (Turing machines)|crossing sequences]] of ''M'' on ''x''. Note that the length of a crossing sequence of ''M'' on ''x'' is at most <math>|\mathcal{C}|</math>: if it is longer than that, then some configuration will repeat, and ''M'' will go into an infinite loop. There are also at most <math>|\mathcal{C}|</math> possibilities for every element of a crossing sequence, so the number of different crossing sequences of ''M'' on ''x'' is

:<math>|S|\le|\mathcal{C}|^{|\mathcal{C}|} \le (2^{c.s(n)})^{2^{c.s(n)}}= 2^{c.s(n).2^{c.s(n)}}< 2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}} = o(n) </math>

According to [[pigeonhole principle]], there exist indexes ''i'' < ''j'' such that <math>\mathcal{C}_i(x)=\mathcal{C}_j(x)</math>, where <math>\mathcal{C}_i(x)</math> and <math>\mathcal{C}_j(x)</math> are the crossing sequences at boundary ''i'' and ''j'', respectively.

Let {{mvar|x'}} be the string obtained from {{mvar|x}} by removing all cells from ''i'' + 1 to ''j''. The machine {{mvar|M}} still behaves exactly the same way on input {{mvar|x'}} as on input {{mvar|x}}, so it needs the same space to compute {{mvar|x'}} as to compute {{mvar|x}}. However, {{math|{{!}}''x' ''{{!}} < {{!}}''x''{{!}}}}, contradicting the definition of {{mvar|x}}. Hence, there does not exist such a language {{mvar|L}} as assumed. □

The above theorem implies the necessity of the [[space-constructible function]] assumption in the [[space hierarchy theorem]].

* [[L (complexity)|L]] = DSPACE(''O''(log&nbsp;''n''))
* [[PSPACE]] = <math>\bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(n^k)</math>
* [[EXPSPACE]] = <math>\bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(2^{n^k})</math>