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 Aaronson

Evidence 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”

Source

99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity— Sean Carroll's Mindscape
Created: 6/13/2026, 12:26:25 AM

Your notes

Loading notes...