EXPTIME vs PSPACE · why no proof exists

The reason: we have hierarchy theorems for time vs time and space vs space, but not for space vs time across different resources.

• Hierarchy theorems compare same-resource bounds. Time vs time, space vs space. Cross-resource (space vs time) comparisons aren't given by hierarchy directly.
• PSPACE = EXPTIME is consistent with what we know. No technique rules it out. Most believe they're distinct, but lack of proof is striking.
• P ⊊ EXPTIME is one of the few proven strict separations. Almost every other "obvious" containment (P vs NP, NP vs PSPACE, PSPACE vs EXPTIME) is open.

• Q1. Why does Time Hierarchy prove P ⊊ EXPTIME but not PSPACE ⊊ EXPTIME?
  Time Hierarchy compares time-bounded classes within the same model. P uses polynomial time; EXPTIME uses exponential time; the hierarchy theorem gives the strict separation. PSPACE uses polynomial space — a different resource. Comparing PSPACE to EXPTIME requires bridging time and space, which the hierarchy theorem doesn't do.
• Q2. Is PSPACE = EXPTIME possible?
  Currently can't be ruled out. Most experts believe PSPACE ⊊ EXPTIME (exponential time should be much larger than polynomial space), but no proof exists. Relativised oracle separations exist but don't transfer.
• Q3. What's the relationship to P vs NP?
  The chain is P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, with P ⊊ EXPTIME being the only proven strict containment. So at least one of the three middle inclusions must be strict, but we don't know which.
• Q4. What does the sandwich theorem tell us?
  SPACE(f) ⊆ TIME(2^O(f)) gives PSPACE ⊆ EXPTIME. The reverse inclusion (EXPTIME ⊆ PSPACE?) isn't known and is widely conjectured false.

Sipser: §9.1, Corollary 9.16. Lecture notes: Module 7 slide 5. Companion problems: P46 (Time Hierarchy), P48 (P ⊊ EXPTIME).