We define a nondeterministic TM (NTM) as a set of states , input alphabet , tape alphabet , and a transition function where
So . Instead of a single transition state, we now have a set of transition states.
We then say a NTM accepts input 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, is the depth of the tree, while is the size of the tree. Formalizing this, we obtain the following theorem.
Proof: Do a breadth-first search on the transition graph, and accept when we reach an accept state. We take the constant to be the maximum number of states in a transition function. The total time is .
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 , what will a DTM take? ? This is as much time as it could take. (Why?)
A specific problem: a path in from to ? If , then NTM needs space by guessing the next vertex. What about a DTM?
Theorem: Graph connectivity .
Proof: Construct the following TM:
- if : if then accept, else reject
- if , if or then accept, else reject
- for each in :
- if accepts, AND accepts, then accept
- for each in :
accepts if a path of length between and in graph , and rejects otherwise.
It needs space per level of recursion to store the names. There are levels of recursion. So total space needed is .
Theorem [Savitch]: .
Proof: Consider the graph of all possible configurations. The number of vertices is . If path from the starting configuration to the ending configuration, it is of length . The space needed by a DTM to check if such path exists is .