An NTM is given an input and runs. One branch of its computation accepts, but 999 other branches reject. What does the NTM do?
AIt rejects, since the majority of branches reject
BIt accepts, since at least one branch accepts
CIt accepts with probability 0.1%, since 1 of 1000 branches accepts
DThe result is undefined — NTMs require all branches to agree
By definition, an NTM accepts if *any* branch of its computation tree accepts. Rejection requires *all* branches to reject (or loop). This is a logical OR over all branches, not a vote or a probability. A probabilistic TM would accept based on the fraction of accepting branches (option C describes BPP-style computation), but that is a different computational model. The NTM is asking: 'does a solution exist?' not 'how many solutions exist?' This is why NP is naturally characterized by NTMs — NP problems have a 'guess-and-verify' structure where one correct guess suffices.
Question 2 Multiple Choice
Which of the following best describes what an NTM adds beyond the power of a DTM?
AIt can compute functions that a DTM cannot — it solves undecidable problems
BIt can decide the halting problem, which a DTM cannot
CIt potentially solves certain problems faster (in fewer steps), but computes the same set of functions as a DTM
DIt eliminates the need for exponential time by parallelizing computation physically
NTMs and DTMs are equivalent in computability — they decide exactly the same set of languages (both characterize Turing-computable functions). An NTM cannot solve the halting problem or any undecidable problem. What NTMs potentially offer is an *efficiency* advantage: an NTM might decide a problem in polynomial time that a DTM requires exponential time to decide. Whether this gap is real for NP vs P problems is precisely the P vs. NP question. Option D misunderstands NTMs as physical parallel computers — they are a theoretical model, not a description of real hardware.
Question 3 True / False
A nondeterministic Turing machine is just a Turing machine that makes random choices between transitions.
TTrue
FFalse
Answer: False
This is the most important misconception about NTMs. A *probabilistic* Turing machine makes random choices, and its acceptance is defined by the probability of accepting branches. An NTM accepts if *any* branch accepts — there is no randomness or probability. Nondeterminism is a theoretical abstraction for 'existential choice': the machine is defined to succeed if there *exists* a sequence of choices leading to acceptance, regardless of how likely or unlikely any single branch is. NTMs and probabilistic TMs define different complexity classes (NP vs. BPP) and answer different questions.
Question 4 True / False
An NTM that runs in polynomial time can generally be simulated by a DTM in polynomial time.
TTrue
FFalse
Answer: False
This is exactly what the P vs. NP question asks — and the answer is unknown. What we do know is that a DTM can simulate an NTM running in time t(n) in time 2^{O(t(n))} by performing BFS over the computation tree. This simulation is exponentially expensive. If the NTM runs in polynomial time (NP), the DTM simulation costs exponential time. Whether there is always a polynomial-time DTM equivalent is the central open problem in computer science.
Question 5 Short Answer
Why is the computation tree the right way to visualize NTM execution, and how does the acceptance condition connect to NP problems in practice?
Think about your answer, then reveal below.
Model answer: An NTM's execution is not a single timeline but a branching tree: at each step where multiple transitions are possible, the machine splits into all possibilities simultaneously. The root is the initial configuration; each path through the tree is one possible sequence of choices. The NTM accepts if any leaf is an accepting state. This models NP problems naturally because NP problems have a 'guess-and-verify' structure: an NTM can nondeterministically guess a candidate solution (one path) and then verify it in polynomial time. If even one guess-path leads to acceptance (a correct solution), the NTM accepts. The difficulty of simulating this with a DTM is that the DTM must search all paths, not just find one.
The tree visualization makes clear why BFS simulation is expensive: the tree can have exponentially many nodes. It also makes clear why acceptance is 'existential' — the NTM is equivalent to asking 'does an accepting leaf exist?' not 'how many accepting leaves exist?' The SAT problem fits perfectly: an NTM guesses a truth assignment (one path down the tree) and verifies it (the rest of that path) — if any assignment satisfies the formula, one branch accepts.