P63 · NP ⊆ EXPTIME via NTM determinization

🔊 Narration

The NTM tree-exploration argument, time analysis, a 3-SAT worked example, and the PSPACE corollary.

🔊 Listen

1 · The theorem

NP ⊆ EXPTIME (Sipser §7.2)

Every NP language can be decided by a deterministic Turing machine running in time 2^{O(n^k)} for some k. Equivalently: every NTM that halts on every branch in time n^k can be deterministically simulated in time 2^{O(n^k)}.

Why anyone cares

This gives the first proven containment in the P ⊆ NP ⊆ EXPTIME chain. Combined with P ⊊ EXPTIME (time hierarchy theorem), it means at least ONE of (P ⊊ NP), (NP ⊊ EXPTIME) is true — we just don't know which.

🔊 Listen

2 · Construction · BFS the nondeterministic computation tree

🔊 Listen

3 · The deterministic simulator

Algorithm DSim — simulate NTM N on input x

Let b = maximum number of nondeterministic choices at any step (a constant of N). N runs for at most T = |x|^k steps on every branch.
Do a breadth-first traversal of N's computation tree, level by level, up to depth T.
At each leaf (depth T): check if it's an accept configuration. If so, accept and halt.
If no leaf accepts: reject.

Time analysis: the tree has fan-out ≤ b and depth ≤ T, so it has at most b^T = b^{|x|^k} leaves. Visiting each takes poly(|x|) time. Total: 2^{O(|x|^k)}. That's EXPTIME.

🔊 Listen

4 · Worked example · 3-SAT with n = 4 variables

An NTM for 3-SAT on n variables

For i = 1 to n: nondeterministically guess assignment of variable x_i (branch ×2).
Deterministically evaluate the formula on the guessed assignment.
Accept iff the formula evaluates to true.

Branching factor b = 2, depth ≤ n. Tree size: 2ⁿ leaves. DSim explores all 2ⁿ assignments — exactly brute force, exponential in n. For n = 4: tree has 16 leaves, DSim checks all 16.

🔊 Listen

5 · Q&A defence notes

Q1. Why BFS and not DFS?
DFS would also work, but BFS keeps the depth bounded at every level — easier to argue that we stop after T levels and reject if no accept seen. Either traversal still costs 2^{O(n^k)}.
Q2. Could we do better than 2^{O(n^k)}?
Not in general — this is the open P vs NP question. If we could simulate any NTM in polynomial deterministic time, P = NP.
Q3. Why is b constant (not part of the input)?
An NTM is a fixed machine, so its transition function δ : Q × Γ → P(Q × Γ × {L,R}) has a fixed maximum image size — let's call it b. The maximum branching factor doesn't depend on the input length.
Q4. What's the memory cost of DSim?
If we store the whole frontier: 2^T configurations × O(T) bytes each = 2^O(T) space. Wasteful. Use Savitch-style recursion or DFS to bring it down to O(T) = polynomial space — this proves NP ⊆ PSPACE as a side benefit.
Q5. So NP ⊆ EXPTIME. Does that mean any NP-complete problem is exponentially solvable?
Yes — at worst. Every NP-complete problem can be solved by exhaustive search in 2^{O(n^k)} time. Real-world algorithms (DPLL for SAT, etc.) use heuristics to do better on practical instances, but the worst case is still exponential as far as anyone knows.