Editing Complexity class (section)

====Nondeterministic Turing machines====
{{Main|Nondeterministic Turing machine}}
[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| A comparison of deterministic and nondeterministic computation. If any branch on the nondeterministic computation accepts then the NTM accepts.]]

The deterministic Turing machine (DTM) is a variant of the nondeterministic Turing machine (NTM). Intuitively, an NTM is just a regular Turing machine that has the added capability of being able to explore multiple possible future actions from a given state, and "choosing" a branch that accepts (if any accept). That is, while a DTM must follow only one branch of computation, an NTM can be imagined as a computation tree, branching into many possible computational pathways at each step (see image). If at least one branch of the tree halts with an "accept" condition, then the NTM accepts the input. In this way, an NTM can be thought of as simultaneously exploring all computational possibilities in parallel and selecting an accepting branch.{{sfn|Sipser|2006|p=48, 150}} NTMs are not meant to be physically realizable models, they are simply theoretically interesting abstract machines that give rise to a number of interesting complexity classes (which often do have physically realizable equivalent definitions). 

The [[time complexity]] of an NTM is the maximum number of steps that the NTM uses on ''any'' branch of its computation.{{sfn|Sipser|2006|p=255}} Similarly, the [[space complexity]] of an NTM is the maximum number of cells that the NTM uses on any branch of its computation.

DTMs can be viewed as a special case of NTMs that do not make use of the power of nondeterminism. Hence, every computation that can be carried out by a DTM can also be carried out by an equivalent NTM. It is also possible to simulate any NTM using a DTM (the DTM will simply compute every possible computational branch one-by-one). Hence, the two are equivalent in terms of computability. However, simulating an NTM with a DTM often requires greater time and/or memory resources; as will be seen, how significant this slowdown is for certain classes of computational problems is an important question in computational complexity theory.