A nondeterministic Turing machine (NTM) and a probabilistic Turing machine (PTM) both branch into multiple computational paths. What is the fundamental difference in how they determine acceptance?
ANTMs use randomness to choose branches; PTMs explore all branches systematically
BNTMs accept if any single branch accepts (existential); PTMs accept if a sufficiently large fraction of branches accept (statistical)
CNTMs are faster because they find the accepting branch immediately; PTMs must run all branches
DPTMs and NTMs accept by the same criterion but differ only in whether they can be simulated efficiently
The distinction is existential vs. statistical acceptance. An NTM asks: does *any* computation path accept? One accepting branch is enough. A PTM asks: does a *large enough fraction* of random computation paths accept? This is why PTMs are said to 'decide' a language with bounded error probability — the fraction of accepting branches must exceed a threshold (e.g., 2/3) for yes-instances and fall below it (e.g., 1/3) for no-instances. Option A has it backwards — PTMs use randomness, NTMs use existential nondeterminism.
Question 2 Multiple Choice
A randomized algorithm for a decision problem gives the correct answer with probability 2/3 on each independent run. An engineer runs it 100 times and takes a majority vote. What happens to the probability of a wrong majority answer?
AIt stays at 1/3, because the underlying error probability of each run is fixed at 1/3
BIt increases, because running more trials compounds the chances of encountering errors
CIt drops exponentially — the probability of a wrong majority answer becomes negligibly small
DIt decreases linearly to approximately 1/300, each run contributing an equal reduction
This is probability amplification. For a majority of 100 runs to be wrong, more than 50 runs must individually err. Since each run errs independently with probability 1/3 < 1/2, the probability that a majority err is bounded by the Chernoff bound and drops exponentially in the number of runs. With 100 runs, the error probability is far below 2^{−50}. The key insight: because each run's error probability is below 1/2, more independent runs make it exponentially harder for errors to dominate.
Question 3 True / False
A probabilistic Turing machine's error probability can be reduced to an arbitrarily small level by running it multiple times independently and taking a majority vote.
TTrue
FFalse
Answer: True
True — this is the probability amplification theorem. As long as each independent run has bounded error probability ε < 1/2, running k runs and taking the majority vote reduces the probability of a wrong answer exponentially in k. This is why the specific error threshold (2/3, 3/4, 0.99) in the definition of PTMs doesn't fundamentally matter — any constant advantage over 1/2 can be amplified to essentially 1.
Question 4 True / False
Probabilistic Turing machines are strictly more computationally powerful than deterministic Turing machines — they can decide languages that no deterministic TM can decide.
TTrue
FFalse
Answer: False
False — this conflates computational power (what can be decided at all) with efficiency (what can be decided in polynomial time). PTMs and deterministic TMs decide the same set of languages in principle; a PTM cannot solve the halting problem or decide any undecidable language. The open question is whether randomness helps with *efficiency*: does BPP = P? Most theorists believe it does, meaning every problem solvable efficiently with randomness also has an efficient deterministic algorithm. PTMs don't expand what is decidable — they may (or may not) expand what is feasibly tractable.
Question 5 Short Answer
Why is probability amplification central to the usefulness of probabilistic Turing machines? What property of the error probability makes it work?
Think about your answer, then reveal below.
Model answer: Amplification works because independent runs' errors are uncorrelated. For the majority vote to be wrong, more than half of k independent runs must err simultaneously. If each run has error probability ε < 1/2, the probability that a majority err falls exponentially in k (by the Chernoff bound). The crucial property is that ε < 1/2 — if errors occurred more than half the time, majority voting would amplify mistakes. Because the algorithm is correct more often than not on each run, accumulating independent samples drives error probability to zero exponentially fast.
This is why the '2/3' threshold in PTM definitions is not special: any constant advantage over random guessing (any ε < 1/2) suffices for amplification to work. The amplification technique means a 51% correct algorithm can be boosted to 1 − 2^{−100} correct with polynomial overhead, which is why the exact error bound in the definition of BPP doesn't matter.