PSPACEhard

PSPACE-hard is a classification used in computational complexity theory to describe the relative difficulty of decision problems. A problem is PSPACE-hard if every problem in PSPACE can be reduced to it in polynomial time. In other words, a polynomial-time algorithm for a PSPACE-hard problem would yield a polynomial-time algorithm for all problems in PSPACE, implying PSPACE would collapse to P if such an algorithm existed for a PSPACE-hard problem. Reductions are typically polynomial-time many-one (Karp) reductions, though some texts discuss broader reductions.

PSPACE is the class of problems solvable using a polynomial amount of memory. PSPACE-hardness does not require the problem itself to be in PSPACE. If a problem is PSPACE-hard and also in PSPACE, it is called PSPACE-complete. The conjunction expresses the standard notion of “as hard as any problem in PSPACE.” Known PSPACE-complete problems include the true quantified boolean formula problem (TQBF). Many other decision problems arising from games, formal verification, and planning are PSPACE-hard, often by reductions from TQBF.

The concept serves to understand the inherent difficulty of problems beyond NP, highlighting that some problems remain intractable even when only polynomial space is available. PSPACE-hardness is a tool for comparing problem difficulty under polynomial-time reductions and for identifying problems that are unlikely to admit efficient, polynomial-time algorithms unless major collapses occur in the standard complexity hierarchy.