Editing Savitch's theorem

{{short description|Relation between deterministic and nondeterministic space complexity}}
{{Use mdy dates|cs1-dates=ly|date=March 2025}}
{{CS1 config|mode=cs2}}
In [[computational complexity theory]], '''Savitch's theorem''', proved by [[Walter Savitch]] in 1970,{{sfnp|Savitch|1970}} gives a relationship between deterministic and non-deterministic [[space complexity]]. It states that for any [[Space-constructible function|space-constructable function]] <math>f\in\Omega(\log(n))</math>,{{sfnp|Sipser|1997}}
  
:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(f\left(n\right)^2\right).</math>

In other words, if a [[nondeterministic Turing machine]] can solve a problem using <math>f(n)</math> space, a [[deterministic Turing machine]] can solve the same problem in the square of that space bound.{{sfnp|Arora|Barak|2009|page=86}}  Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven [[exponential time hypothesis]]), Savitch's theorem shows that it has a markedly more limited effect on space requirements.{{sfnp|Arora|Barak|2009|page=92}}

The theorem can be [[Oracle machine|relativized]]. That is, for any oracle, replacing every "Turing machine" with "oracle Turing machine" would still result in a theorem.{{sfnp|Balcázar|Díaz|Gabarró|1988|loc=Theorem 2.9}}

== Proof ==
The proof relies on an algorithm for [[st-connectivity|STCON]], the problem of determining whether there is a path between two vertices in a [[Graph (discrete mathematics)#Directed graph|directed graph]], which runs in <math>O\left((\log n)^2\right)</math> space for <math>n</math> vertices. The basic idea of the algorithm is to solve [[recursion|recursively]] a somewhat more general problem, testing the existence of a path from a vertex <math>s</math> to another vertex <math>t</math> that uses at most <math>k</math> edges, for a parameter <math>k</math> given as input. STCON is a special case of this problem where <math>k</math> is set large enough to impose no restriction on the paths (for instance, equal to the total number of vertices in the graph, or any larger value). To test for a <math>k</math>-edge path from <math>s</math> to <math>t</math>,
a deterministic algorithm can iterate through all vertices <math>u</math>, and recursively search for paths of half the length from <math>s</math> to <math>u</math> and from <math>u</math> to <math>t</math>.{{sfnp|Papadimitriou|1993}}
This algorithm can be expressed in pseudocode (in [[Python (programming language)|Python]] syntax) as follows:
<syntaxhighlight lang="python">
def stcon(s, t) -> bool:
    """Test whether a path of any length exists from s to t"""
    return k_edge_path(s, t, n)  # n is the number of vertices

def k_edge_path(s, t, k) -> bool:
    """Test whether a path of length at most k exists from s to t"""
    if k == 0:
        return s == t
    if k == 1:
        return (s, t) in edges
    for u in vertices:
        if k_edge_path(s, u, floor(k / 2)) and k_edge_path(u, t, ceil(k / 2)):
            return True
    return False
</syntaxhighlight>
Because each recursive call halves the parameter <math>k</math>, the number of levels of recursion is <math>\lceil\log_2 n\rceil</math>. Each level requires <math>O(\log n)</math> bits of storage for its function arguments and [[local variable]]s: <math>k</math> and the vertices <math>s</math>, <math>t</math>, and <math>u</math> require <math>\lceil\log_2 n\rceil</math> bits each. The total [[Space_complexity#Auxiliary_space_complexity|auxiliary space complexity]] is thus <math>O\left((\log n)^2\right)</math>.{{sfnp|Papadimitriou|1993}} The input graph is considered to be represented in a separate read-only memory and does not contribute to this auxiliary space bound. Alternatively, it may be represented as an [[implicit graph]]. Although described above in the form of a program in a high-level language, the same algorithm may be implemented with the same asymptotic space bound on a [[Turing machine]].

This algorithm can be applied to an implicit graph whose vertices represent the configurations of a nondeterministic Turing machine and its tape, running within a given space bound <math>f(n)</math>. The edges of this graph represent the nondeterministic transitions of the machine, <math>s</math> is set to the initial configuration of the machine, and <math>t</math> is set to a special vertex representing all accepting halting states. In this case, the algorithm returns true when the machine has a nondeterministic accepting path, and false otherwise. The number of configurations in this graph is <math>O(2^{f(n)})</math>, from which it follows that applying the algorithm to this implicit graph uses space <math>O(f(n)^2)</math>. Thus by deciding connectivity in a graph representing nondeterministic Turing machine configurations, one can decide membership in the language recognized by that machine, in space proportional to the square of the space used by the Turing machine.{{sfnp|Papadimitriou|1993}}

== Corollaries ==
Some important corollaries of the theorem include:
; [[PSPACE]] = [[NPSPACE]]
: That is, the languages that can be recognized by deterministic polynomial-space Turing machines and nondeterministic polynomial-space Turing machines are the same. This follows directly from the fact that the square of a polynomial function is still a polynomial function.{{sfnp|Papadimitriou|1993}} It is believed that a similar relationship  does not exist between the polynomial time complexity classes, [[P (complexity)|P]] and [[NP (complexity)|NP]], although this is still an [[P = NP problem|open question]].
; [[NL (complexity)|NL]] ⊆ [[L (complexity)|L<sup>2</sup>]]
: That is, all languages that can be solved nondeterministically in logarithmic space can be solved deterministically in the complexity class <math display=block>\mathsf{\color{Blue}L}^2 =\mathsf{DSPACE}\left(\left(\log n\right)^2\right).</math> This follows from the fact that STCON is [[NL-complete]].

==See also==
*{{annotated link|Immerman–Szelepcsényi theorem}}

== Notes ==
{{Reflist}}

== References ==
{{Refbegin}}
* {{citation |last1=Arora |first1=Sanjeev |authorlink1=Sanjeev Arora |last2=Barak |first2=Boaz |year=2009 |title=Computational Complexity: A Modern Approach |publisher=[[Cambridge University Press]] |isbn=978-0-521-42426-4 |zbl=1193.68112}}
* {{citation |last1=Balcázar |first1=José Luis |title=Structural Complexity I |last2=Díaz |first2=Josep |last3=Gabarró |first3=Joaquim |publisher=Springer-Verlag |year=1988 |isbn=3-540-18622-0}}
* {{citation |last=Papadimitriou |first=Christos |author-link=Christos Papadimitriou |contribution=Section 7.3: The Reachability Method |year=1993 |title=Computational Complexity |edition=1st |publisher=Addison Wesley |pages=149–150 |isbn=0-201-53082-1}}
* {{citation |last=Savitch |first=Walter J. |author-link=Walter Savitch |year=1970 |title=Relationships between nondeterministic and deterministic tape complexities |journal=Journal of Computer and System Sciences |volume=4 |issue=2 |pages=177–192 |doi=10.1016/S0022-0000(70)80006-X |hdl=10338.dmlcz/120475 |hdl-access=free}}
* {{citation |last=Sipser |first=Michael |author-link=Michael Sipser |contribution=Section 8.1: Savitch's Theorem |year=1997 |title=Introduction to the Theory of Computation |url=https://archive.org/details/introductiontoth00sips/page/279 |url-access=registration |publisher=PWS Publishing |pages=[https://archive.org/details/introductiontoth00sips/page/279 279–281] |isbn=0-534-94728-X}}
{{Refend}}

==External links==
* Lance Fortnow, ''[http://blog.computationalcomplexity.org/2003/05/foundations-of-complexity-lesson-18.html Foundations of Complexity, Lesson 18: Savitch's Theorem]''. Accessed 2009-09-09.
* [[Richard J. Lipton]], ''[http://rjlipton.wordpress.com/2009/04/05/savitchs-theorem/ Savitch’s Theorem]''. Gives a historical account on how the proof was discovered.

[[Category:Structural complexity theory]]
[[Category:Theorems in computational complexity theory]]