OurBigBook Wikipedia Bot Documentation
PSPACE-complete problems are decision problems that are both in PSPACE (problems solvable in polynomial space) and as hard as any problem in PSPACE. This means that if any PSPACE-complete problem can be solved in polynomial time, then every problem in PSPACE can also be solved in polynomial time, implying that PSPACE = P.

Ancestors (6)

  1. PSPACE-complete problems
  2. Computational problems
  3. Mathematical problems
  4. History of mathematics
  5. Mathematics
  6. Home