2.1 The non-deterministic Turing machine (NTM)

One change to the model: the transition function returns a set of possible moves —

δ : Q × Γ → 𝒫(Q × Γ × {L, R})

At each step the machine may follow any of the allowed moves, so a single input generates a tree of computations rather than a single path.

Acceptance rule: the NTM accepts x iff at least one branch accepts. Running time = the depth of the tree (length of the longest branch) as a function of |x|.

One accepting leaf is enough — the whole input is accepted.

2.2 Three ways to picture non-determinism

1. Lucky guesser: the machine always magically guesses a move leading to acceptance, if one exists.
2. Unbounded parallelism: all branches explored simultaneously, free of charge.
3. Guess-and-verify (the practical one): an NTM computation = guess a certificate non-deterministically, then verify it deterministically.

Picture 3 is exactly why the two definitions of NP coincide:

NP = languages accepted by NTMs in polynomial time = languages with polynomial-time verifiable certificates.

Proof sketch: (⟸) An NTM can guess the certificate (one symbol per step) then run the verifier. (⟹) A verifier can take the sequence of choices of an accepting branch as the certificate and replay it deterministically. ∎

Example — SAT on an NTM: guess an assignment (n binary choices, n steps), evaluate the formula (polynomial). Total: polynomial non-deterministic time. The 2ⁿ possible assignments form the branches of the tree; satisfiability = some leaf accepts.

2.3 Determinism vs non-determinism: what simulation costs

A DTM can simulate an NTM by exploring the computation tree (breadth-first to avoid infinite branches):

NTM time t(n) ⟹ DTM time 2^O(t(n))

So NP ⊆ EXP. No better-than-exponential general simulation is known — and whether the exponential blow-up is necessary is precisely P vs NP. Non-determinism adds nothing for decidability (NTMs decide the same languages as DTMs); the entire question is the cost.

2.4 Non-determinism and space — a startling contrast

For space, the gap is provably tiny:

Savitch's theorem: NSPACE(f(n)) ⊆ SPACE(f(n)²) for f(n) ≥ log n.

Hence NPSPACE = PSPACE — non-determinism does not help polynomial space! (Squaring a polynomial is a polynomial.) The proof is a clever divide-and-conquer over configurations: reachability within 2ᵏ steps is checked by recursively asking reachability within 2ᵏ⁻¹ steps through a guessed midpoint, reusing space across the two halves.

This asymmetry (space is reusable, time is not) is among the most quotable facts in the course.

2.5 co-NP — non-determinism's mirror

co-NP = languages whose complements are in NP — problems whose NO answers have short certificates. Example: UNSAT (a certificate for "satisfiable" is easy, but for "unsatisfiable"?). TAUTOLOGY ("true under every assignment") is co-NP-complete.

A problem in NP ∩ co-NP has short certificates for both YES and NO — historically a strong hint of an undiscovered polynomial algorithm (primality sat there for decades before AKS; factoring sits there today, which is exactly why cryptographers watch this class nervously).

2.6 Worked example — an NTM for SUBSET-SUM, written properly

SUBSET-SUM: given numbers a₁...aₙ and target T, does some subset sum to T?

Phase 1 (guess):   for i = 1..n, nondeterministically write bᵢ ∈ {0, 1}
Phase 2 (verify):  compute Σ bᵢ·aᵢ deterministically; accept iff it equals T

Phase 1 takes n nondeterministic steps; phase 2 is ordinary arithmetic — polynomial in the input's bit-length. The computation tree has 2ⁿ leaves, one per subset, and the machine accepts iff some leaf accepts — i.e. iff a valid subset exists. Every guess-and-verify NP-membership argument in this course compiles to exactly this two-phase shape, and in exams you may present it at exactly this level of abstraction.

2.7 The deterministic simulation, with the cost accounted

Claim: an NTM M with time bound t(n) and at most b choices per step (b is a constant fixed by δ) is simulated by a DTM in time 2^O(t(n)). Sketch: the computation tree has ≤ b^t(n) branches, each of length ≤ t(n). Enumerate branches by their choice strings s ∈ {1..b}^t(n); for each s, deterministically replay M following s; accept iff any replay accepts. Cost: b^t · O(t) = 2^O(t). ∎ Replaying by choice string — rather than physically walking a tree — is also the bridge in the verifier ⟺ NTM equivalence: **the choice string of an accepting branch is the certificate.**

2.8 DTM vs NTM at a glance

The acceptance asymmetry in row four is precisely why NP and co-NP are not obviously equal: swapping the accept and reject states of an NTM does not complement its language.

2.9 Savitch's theorem — the proof idea in exam-reproducible form

Define the predicate REACH(C₁, C₂, k): "configuration C₂ is reachable from C₁ in at most 2ᵏ steps".

REACH(C1, C2, k):
    if k = 0:  check C1 = C2 or C1 yields C2 in one step
    else:      for every possible middle configuration Cm:        ← try all, REUSING space
                   if REACH(C1, Cm, k−1) and REACH(Cm, C2, k−1):  return true

Acceptance of an f(n)-space NTM = REACH(start, accept, O(f(n))), since such a machine has 2^O(f(n)) configurations. The space bill: recursion depth O(f(n)), each frame stores one configuration of size O(f(n)) → O(f(n)²) total. The two recursive calls run sequentially in the same workspace — space reuse is the entire theorem. ∎

Exam pointer

Expected questions: ① "Define an NTM and its acceptance; how does it differ from a DTM?" — §2.1 plus §2.8's table; ② "Show the two definitions of NP coincide" — §2.2's sketch with the choice-string remark of §2.7; ③ "State Savitch's theorem and its consequence" — NSPACE(f) ⊆ SPACE(f²), hence PSPACE = NPSPACE; give the midpoint recursion if the idea is asked.

Self-check

1. An NTM has one accepting branch and a million rejecting ones. Does it accept?
2. Why must the certificate in the verifier definition be polynomially short?
3. Where exactly does the 2^O(t) cost arise in the deterministic simulation of an NTM?
4. Write the space recurrence S(k) = S(k−1) + O(f(n)) from Savitch's proof and solve it.
5. Give a problem in NP ∩ co-NP and justify both memberships. (Factoring's decision version "does n have a non-trivial factor ≤ k?" — YES-certificate: such a factor; NO-certificate: the full prime factorisation.)