Background

P vs. PSPACE is one of the major open problems in computational complexity theory. P is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time, while PSPACE is the class of problems solvable using polynomial space (memory). Most complexity theorists believe that P ≠ PSPACE, but proving this remains an extremely challenging problem.

Unlike P vs. NP, which is one of the seven Millennium Prize Problems with a $1 million reward, P vs. PSPACE has received somewhat less attention but is still considered a fundamental question in theoretical computer science. The problem has remained unsolved since these complexity classes were defined in the 1970s.

Resolution Criteria

This market resolves to the number of years after 2000 when a proof regarding the P vs. PSPACE problem is published and achieves consensus in the theoretical computer science community. Specifically:

• If a proof is published in 2025, this market resolves to 25

• If a proof is published in 2030, this market resolves to 30

• If a proof is published in 2050, this market resolves to 50

For a proof to be considered valid, it must be:

1. Published in a peer-reviewed journal or conference, or as a widely accepted preprint

2. Verified by multiple experts in complexity theory

3. Generally accepted by the theoretical computer science community

If the problem remains unresolved by 2125 (100 years after 2025), the market will remain open.