Editing PSPACE (section)

== Other characterizations ==
An alternative characterization of PSPACE is the set of problems decidable by an [[alternating Turing machine]] in polynomial time, sometimes called APTIME or just AP.<ref name=AB100>Arora & Barak (2009) p.100</ref>

A logical characterization of PSPACE from [[descriptive complexity]] theory is that it is the set of problems expressible in [[second-order logic]] with the addition of a [[transitive closure]] operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from [[PH (complexity)|PH]].

A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular [[interactive proof system]], the one defining the class [[IP (complexity)|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 (complexity)|QIP]].<ref>{{cite arXiv|title=QIP = PSPACE|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4-link=John Watrous (computer scientist)|author4=John Watrous|eprint=0907.4737|date=July 2009|class=quant-ph}}</ref>

PSPACE is also equal to P<sub>CTC</sub>, problems solvable by classical computers using [[closed timelike curve]]s,<ref>{{cite journal|author=S. Aaronson | arxiv=quant-ph/0502072| title= NP-complete problems and physical reality |journal=SIGACT News|date=March 2005| doi=10.1145/1052796.1052804|bibcode=2005quant.ph..2072A| s2cid=18759797}}.</ref> as well as to BQP<sub>CTC</sub>, problems solvable by [[quantum computer]]s using closed timelike curves.<ref>{{cite journal | doi=10.1098/rspa.2008.0350|bibcode = 2009RSPSA.465..631A | title=Closed timelike curves make quantum and classical computing equivalent | year=2009 | last1=Watrous | first1=John | last2=Aaronson | first2=Scott | journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume=465 | issue=2102 | pages=631 |arxiv = 0808.2669 |s2cid = 745646 }}</ref>