# Nondeterminism & Savitch’s Theorem

Nondeterminism

We define a nondeterministic TM (NTM) as a set of states $Q$, input alphabet $\Sigma$, tape alphabet $\Gamma$, and a transition function $\delta$ where

$\delta: Q\times \Gamma \rightarrow (Q \times \Gamma \times \{L,R\})*$

So $\delta(q,\gamma) = \{(q_1, \gamma_1, L), (q_2, \gamma_2, L), (q_3, \gamma_3, R), \ldots \}$. Instead of a single transition state, we now have a set of transition states.

We then say a NTM accepts input $x$ if there exists ANY possible path to an accept state. There could be many paths to reject states, but as long as there is one path to an accept state, the NTM accepts.

If we consider the transition tree of a NTM, $NTIME$ is the depth of the tree, while $DTIME$ is the size of the tree. Formalizing this, we obtain the following theorem.

Theorem $NTIME(t(n)) \subseteq DTIME(C^{t(n)})$.

Proof: Do a breadth-first search on the transition graph, and accept when we reach an accept state. We take the constant $C$ to be the maximum number of states in a transition function. The total time is $C^{t(n)} = 2^{O(t(n))}$.

Note that this implies that nondeterminism does not grant the power to solve any additional problems that deterministic algorithms cannot. However, nondeterminism may decrease the amount of time or space needed.

What about space? If a NTM takes space $s(n)$, what will a DTM take? $C^{s(n)}$? This is as much time as it could take. (Why?)

A specific problem: $\exists$ a path in $G$ from $s$ to $t$? If $|V|=n$, then NTM needs $O(\log n)$ space by guessing the next vertex. What about a DTM?

Theorem: Graph connectivity $\in DSPACE(O(\log^2n))$.

Proof: Construct the following TM:

• $PATH(a, b, k)$:
• if $k=0$: if $a=b$ then accept, else reject
• if $k=1$, if $(a,b)\in E$ or $a=b$ then accept, else reject
• else:
• for each $c\neq a,b$ in $V$:
• if $PATH(a,c, \lfloor \frac{k}{2}\rfloor)$ accepts, AND $PATH(c,b, \lceil \frac{k}{2}\rceil)$ accepts, then accept
• reject

$PATH(a,b,k)$ accepts if $\exists$ a path of length $\le k$ between $a$ and $b$ in graph $G=(V,E)$, and rejects otherwise.

It needs space $O(\log n)$ per level of recursion to store the names. There are $\log_2k\le \log_2n$ levels of recursion. So total space needed is $O(\log^2n)$.

Theorem [Savitch]: $NSPACE(s(n))\subseteq DSPACE(O(s(n)^2))$.

Proof: Consider the graph of all possible configurations. The number of vertices is $|V|=|Q|\times (s(n) + n) \times |\Gamma|^{s(n)}$. If $\exists$ path from the starting configuration to the ending configuration, it is of length $\le |V|-1$. The space needed by a DTM to check if such path exists is $O(\log^2|V|)=O((s(n)+\log(s(n)))^2)=O(s(n)^2)$.