Editing PSPACE (section)

== PSPACE-completeness ==
{{main|PSPACE-complete}}
A language ''B'' is ''[[PSPACE-complete]]'' if it is in PSPACE and it is PSPACE-hard, which means for all ''A'' ∈ PSPACE, <math>A \leq_\text{P} B</math>, where <math>A \leq_\text{P} B</math> means that there is a [[polynomial-time many-one reduction]] from ''A'' to ''B''. PSPACE-complete problems are of great importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a simple solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem.<ref name=AB83>Arora & Barak (2009) p.83</ref>

An example of a PSPACE-complete problem is the [[quantified Boolean formula problem]] (usually abbreviated to '''QBF''' or '''TQBF'''; the '''T''' stands for "true").<ref name=AB83/>