Skip to content

Problems News About Submit

← All problems

P versus PSPACE

Let $P$ be deterministic polynomial time and $PSPACE$ deterministic polynomial space.

Is $P = PSPACE$ ?

Abstract

PSPACE permits polynomial memory and potentially exponential time. Quantified Boolean Formula is PSPACE-complete, providing a concrete representative for the question.

Background and progress

Polynomial-space computation emerged as a central resource-bounded model.
Quantified Boolean Formula was shown PSPACE-complete.
The time and space hierarchy theorems separate some resource bounds, but do not separate P from PSPACE.

Reference papers

Complexity Zoo: PSPACEScott AaronsonComplexity Zoo · 2002 ↗

© 2026 OpenTCS · All rights reserved.

DocsGitHub Twitter

Organizer

Boyuan Wang

Minghan Wang

Bochao Li