Interactive Proofs and the PSPACE Landscape: A Practical Investigation of the Space-Time Barrier

Abstract

The relationship between deterministic polynomial time (P) and polynomial space (PSPACE) is one of the foundational open problems in computational complexity theory. While proving P = PSPACE remains elusive and is widely believed to be false, the characterizations of PSPACE have yielded profound insights into modern computer science, specifically cryptography and zero-knowledge proofs. This paper surveys the landscape of PSPACE, examines the three fundamental barriers preventing resolution, and presents original systems-level experiments in C and Python that make the space-time tradeoff at the heart of the problem tangible and measurable.