Savitch's Theorem

The set of Savitch or Theorem of Savitch is a sentence from the complexity theory , which in 1970 by Walter Savitch was proved. It says that a problem that can be solved by a nondeterministic Turing machine with a certain space complexity can be solved on a deterministic Turing machine with a square higher space bound.

One consequence of Savitch's Theorem is that PSPACE and NPSPACE are equal .

statement

Be a function that can be constructed with space . Then: ${\displaystyle s:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle s(n)\in \Omega (\log(n))}$

${\displaystyle {\text{NSPACE}}(s(n))\subseteq {\text{DSPACE}}((s(n))^{2})}$

Proof idea

Let us assume , d. H. there is a nondeterministic Turing machine that takes up space and accepts exactly language . Due to the limited space, it can only assume different configurations , the number of their states and the number of different ribbon symbols denoting. So if this machine accepts an input of length , (if and only then) there is also an accepting run with fewer than computing steps. Let's consider a predicate ${\displaystyle L\in {\mbox{NSPACE}}(s(n))}$ ${\displaystyle M}$ ${\displaystyle s(n)}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle |Q|\cdot n\cdot s(n)\cdot |\Gamma |^{s(n)}}$ ${\displaystyle |Q|}$ ${\displaystyle |\Gamma |}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle |Q|\cdot n\cdot s(n)\cdot |\Gamma |^{s(n)}}$

${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i){\stackrel {\text{def}}{\iff }}}$Based on the configuration, the NTM can achieve the configuration within computing steps . ${\displaystyle M}$ ${\displaystyle \alpha }$ ${\displaystyle 2^{i}}$ ${\displaystyle \beta }$

Identify the initial configuration of the NTM when entering the word and the accepting hold configuration. Then we can formulate " accepted " (with a suitable constant depending on and ) as: ${\displaystyle {\mbox{Start}}(w)}$ ${\displaystyle w}$ ${\displaystyle {\mbox{Accept}}}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle C}$ ${\displaystyle s}$ ${\displaystyle M}$

${\displaystyle {\mbox{Reach}}({\mbox{Start}}(w),{\mbox{Accept}},C\cdot s(n))\iff w\in L}$.

We know that a deterministic Turing machine with space requirements can calculate whether it is true. Also has the property ${\displaystyle s(n)}$ ${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,1)}$ ${\displaystyle {\mbox{Reach}}}$

${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i+1)\iff }$there is an intermediate configuration with and . ${\displaystyle \gamma }$ ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$

A deterministic Turing machine can calculate by enumerating all possible configurations and calculating and for each (one after the other) . For this purpose (for suitable ) band cells for and band cells for the calculation of or are sufficient . In particular, such a DTM can determine with space requirements whether and thus whether . ${\displaystyle {\mbox{Reach}}(\alpha ,\beta ,i+1)}$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$ ${\displaystyle C'}$ ${\displaystyle C'\cdot s(n)}$ ${\displaystyle \gamma }$ ${\displaystyle C'\cdot i\cdot s(n)}$ ${\displaystyle {\mbox{Reach}}(\alpha ,\gamma ,i)}$ ${\displaystyle {\mbox{Reach}}(\gamma ,\beta ,i)}$ ${\displaystyle C\cdot C'\cdot s^{2}(n)}$ ${\displaystyle {\mbox{Reach}}({\mbox{Start}}(w),{\mbox{Accept}},C\cdot s(n))}$ ${\displaystyle w\in L}$

The choice of suitable constants is possible in particular because of . ${\displaystyle C,C'}$ ${\displaystyle s(n)\in \Omega (\log n)}$

See also

• List of theorems of computer science

literature

• Walter Savitch: Relationships between nondeterministic and deterministic tape complexities . In: Journal of Computer and System Sciences . tape 4 , no. 2 . Elsevier, 1970, ISSN  0022-0000 , pp. 177-192 , doi : 10.1016 / S0022-0000 (70) 80006-X .