factual
P, PSPACE and Exponential Time Hierarchy
Polynomial time (P) is contained in polynomial space (PSPACE), which is contained in exponential time, because a serial computer using N bits of memory can pass through at most 2-to-the-N states before halting or looping; we believe each containment is strict but have only proven that exponential time is strictly larger than polynomial time.
factualpending
Speaker
Scott AaronsonEvidence Quote
“polynomial time is contained in polynomial space, which is contained in exponential time. And the reason polynomial space is contained in exponential time is that, well, if I have, let's say, N bits of memory, then my computer can pass through at most 2 to the N power possible states”
Created: 6/13/2026, 12:26:25 AM
Your notes
Loading notes...