Nondeterminism and 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 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 decision tree of a TM, 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.

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(s(n)^2)

Proof: Consider the graph of all possible configurations. The number of vertices is |V|=|Q|\times s(n)\times C^{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).

This result has been improved for undirected graph connectivity. Namely, connectivity problem for undirected graph can be solved using space O(\log n) [REINGOLD]. Graph connectivity problem can also be solved with randomness in space O(\log n).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s