recognizable by a particular interactive proof system, the one defining the class IP. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language. PSPACE can be characterized as the quantum complexity class QIP. PSPACE is also equal to PCTC, problems solvable by classical computers using closed timelike curves, as well as to BQPCTC, problems solvable by quantum computers using closed timelike curves. PSPACE-completeness A language B is PSPACE-complete if it is in PSPACE and it is PSPACE-hard, which means for all A ∈ PSPACE, , where 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"). Notes References Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294. Chapter 19: Polynomial space, pp. 455–490. Chapter 8: Space Complexity Complexity classes