P48 · P ⊊ EXPTIME

🔊 Listen

1 · P ⊊ EXPTIME · one of the few proven separations

Of all the famous class containments — P vs NP, NP vs PSPACE, PSPACE vs EXPTIME — only one is unconditionally proven strict: P ⊊ EXPTIME. Almost everything else around it is open.

Proof via Time Hierarchy

The Time Hierarchy Theorem (Problem 46) says TIME(f) ⊊ TIME(f · log f) for time-constructible f. So TIME(n^k) ⊊ TIME(n^k · log n) for each k. Taking the union over all k gives P. Setting f = 2ⁿ: TIME(2ⁿ) ⊊ TIME(2ⁿ · n). In particular, TIME(2ⁿ) strictly contains some language not in TIME(n^k) for any k, hence not in P.

Explicit witnesses

The diagonal language from the Time Hierarchy proof — "TM M halts on ⟨M⟩ within 2ⁿ steps" — is in EXPTIME but not in P. Naturally-arising examples include generalised chess (EXPTIME-complete) and various game-theoretic problems.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

P ⊊ EXPTIME doesn't imply P ⊊ NP. Determinism and nondeterminism are different axes. P ⊊ EXPTIME compares deterministic-time bounds; P ⊊ NP would compare det vs nondet.
EXPTIME-complete problems aren't in P. If they were, P = EXPTIME, contradicting the separation. So generalised chess, succinct circuit problems, etc., really are outside P.
The diagonal witness is artificial; natural witnesses are EXPTIME-complete games. Both prove P ⊊ EXPTIME, but only the latter give compelling examples.

🔊 Listen

4 · Q&A defence notes

Q1. What's an explicit language in EXPTIME \ P?
The "halt within 2ⁿ steps" diagonaliser from the Time Hierarchy proof. Concrete natural examples: generalised chess (EXPTIME-complete), succinct PROBLEM-SUCCINCT (any P-complete or PSPACE-complete problem with succinct encoding moves up one level).
Q2. Why is P ⊊ EXPTIME provable but P ⊊ NP not?
The Time Hierarchy compares time bounds within the same machine model (deterministic). NP uses nondeterminism — a different machine model. We don't have a hierarchy theorem connecting deterministic time to nondeterministic time of the same bound.
Q3. Are there separations between P and PSPACE?
P ⊊ PSPACE is open. If we could prove P ⊊ PSPACE we'd also resolve P vs NP (since NP ⊆ PSPACE). Most believe P ⊊ PSPACE but no proof is known.
Q4. What can we conclude from P ⊊ EXPTIME and NP ⊆ PSPACE ⊆ EXPTIME?
At least one of: NP ⊊ PSPACE, PSPACE ⊊ EXPTIME, or NP = EXPTIME is true (otherwise we'd contradict P ⊊ EXPTIME). But we don't know which.

🔊 Listen

5 · Where to read more

Sipser: Corollary 9.16 (P ⊊ EXPTIME). Lecture notes: Module 7 slide 5. Companion problems: P46 (Time Hierarchy), P47 (NL ⊊ PSPACE), P63 (NP ⊆ EXPTIME).