PSPACE - PSPACE-completeness

PSPACE-completeness

A language B is PSPACE-complete if it is in PSPACE and it is PSPACE-hard, which means for all A PSPACE, A B, where A B 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.

An example of a PSPACE-complete problem is the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true").

Read more about this topic:  PSPACE