P versus PSPACE

A computer can erase its scratch work and reuse the same memory while trying many possibilities. With three on/off switches, it can inspect all eight settings one at a time, storing only the current setting and enough scratch work to check it. More switches make the search much longer without requiring a record of every setting. P versus PSPACE asks whether reusing a moderate amount of memory can solve any decision problem that every moderate-time algorithm fails to solve. Here moderate means bounded by a fixed power of the input length, such as its square or cube; this is a polynomial bound.[1] [3]

Can limited scratch memory, reused over a long computation, decide more problems than a polynomial number of steps? The classes P and PSPACE formalize this question for ordinary deterministic Turing machines. With input length $n$, a polynomial bound has the form $O(n^k)$ for some fixed constant $k$ that may depend on the problem. P imposes such a bound on time; PSPACE imposes it on working storage. For example, enumerating the $2^m$ assignments of $m$ Boolean variables needs only one $m$-bit assignment counter plus checking workspace, not all assignments stored together. Every polynomial-time computation uses at most polynomial space, so $\mathrm P\subseteq\mathrm{PSPACE}$. The open question is whether this containment is strict.[1] [3]

Polynomial time and polynomial space are still not proved different.[1] [2] [3]

Separating these classes requires one polynomial-space decision problem with no polynomial-time algorithm, excluding every fixed time exponent. Williams’s 2025 square-root-space simulation yields near-quadratic time lower bounds for certain space-bounded problems, an important narrower result that leaves larger polynomial time bounds possible. A machine given a special external answer source operates in an oracle model; separations there do not by themselves settle ordinary computation.[1] [2] [3]

Memory and time place different limits on what a computer can do. A search may fit in memory but take far too long to finish. Understanding whether this difference is unavoidable for some problems would explain whether abundant patience can compensate for limited working storage in a way that no faster algorithm can match. A slow search alone does not prove such a limit.[1] [3]

Fully quantified Boolean formulas encode a succession of choices, some asking whether a successful option exists and others requiring success for every option. They can be evaluated by exploring branches and retaining only the current branch and intermediate answers; this problem is PSPACE-complete. A polynomial-time algorithm for it would put all PSPACE problems in P. The connection makes the time–space question concrete: can the effort of evaluating all these dependent choices always be avoided while still returning the right answer?[1] [3]