Editing Nondeterministic Turing machine (section)

==Computational equivalence with DTMs==
Any computational problem that can be solved by a DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the [[time complexity]] may not be the same.

===DTM as a special case of NTM===
NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM.

===DTM simulation of NTM===
It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting a string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way.

====Multiplicity of configuration states====
One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever the transition relation defines multiple continuations.

====Multiplicity of tapes====
Another construction simulates NTMs with 3-tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree.<ref>{{cite book |last1=Lewis |first1=Harry R. |author1-link=Harry R. Lewis |last2=Papadimitriou |first2=Christos |author2-link=Christos Papadimitriou |year=1981 |chapter=Section 4.6: Nondeterministic Turing machines |title=Elements of the Theory of Computation |publisher=Prentice-Hall |place=Englewood Cliffs, New Jersey |edition=1st |pages=204–211 |isbn=978-0132624787 |url-access=registration |url=https://archive.org/details/elementsoftheory0000lewi}}</ref> The 3-tape DTMs are easily simulated with a normal single-tape DTM.

====Time complexity and P versus NP====
{{Main|P versus NP problem}}
In the second construction, the constructed DTM effectively performs a [[breadth-first search]] of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The [[P = NP problem]], the most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time.