KnowraNondeterministic Turing machineLinked fromLinked fromThe 5 pages that link to Nondeterministic Turing machine, each with the reason it gives.All 5Related 3Narrower topic 1Compared with 1Turing machineCompared with: Its branching computation provides a contrasting way to define machine behavior.P versus NP problemRelated: This model gives the original machine-based definition of NP.Leonid LevinRelated: NP-completeness is defined using efficient verification or nondeterministic computation.Savitch's theoremNarrower topic: The theorem begins with computations that accept when at least one branch accepts.Immerman–Szelepcsényi theoremRelated: Acceptance means at least one branch succeeds; complementing that condition is the theorem’s challenge.