Editing PSPACE-complete

{{Short description|Type of decision problem in computer science}}
In [[computational complexity theory]], a [[decision problem]] is '''PSPACE-complete''' if it can be solved using an amount of memory that is polynomial in the input length ([[PSPACE|polynomial space]]) and if every other problem that can be solved in polynomial space can be [[Polynomial-time reduction|transformed to it in polynomial time]].  The problems that are PSPACE-complete can be thought of as the hardest problems in [[PSPACE]], the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

Problems known to be PSPACE-complete include determining properties of [[regular expression]]s and [[context-sensitive grammar]]s, determining the truth of [[quantified Boolean formula problem|quantified Boolean formulas]], step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.

==Theory==
A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem.{{r|garey-johnson}}

The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes [[P (complexity)|P]] (polynomial time) and [[NP (complexity)|NP]] (non-deterministic polynomial time), but that is not known.{{r|arora-barak}} It is known that they lie outside of the class [[NC (complexity)|NC]], a class of problems with highly efficient [[parallel algorithm]]s, because problems in NC can be solved in an amount of space polynomial in the [[logarithm]] of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the [[space hierarchy theorem]].

The transformations that are usually considered in defining PSPACE-completeness are polynomial-time [[many-one reduction]]s, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using [[Turing reduction]]s, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems.{{r|watanabe-tang}} Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.{{r|hitchcock-pavan}}

A version of the [[Berman–Hartmanis conjecture]] for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time [[bijection]]s.{{r|berman-hartmanis}}

==Examples==
{{Main|List of PSPACE-complete problems}}

===Formal languages===
Given a [[regular expression]] <math>R</math>, determining whether it generates every string over its alphabet is PSPACE-complete.{{r|hunt}}

The first known PSPACE-complete problem was the [[word problem (computability)|word problem]] for [[deterministic computation|deterministic]] [[context-sensitive grammar]]s. In the word problem for context-sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and {{harvtxt|Kuroda|1964}} showed that every (possibly non-deterministic) program computable in [[linear space]] could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism.{{r|kuroda}} In 1970, [[Savitch's theorem]] showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE.{{r|garey-johnson}}

===Logic===
A standard PSPACE-complete problem, used in many other PSPACE-completeness results, is the [[quantified Boolean formula problem]], a generalization of the [[Boolean satisfiability problem]]. The quantified Boolean formula problem takes as input a Boolean expression, with all of its variables quantified either universally or existentially, for example:
<math display=block>\exists x_1 \, \forall x_2 \, \exists x_3 \, \forall x_4: (x_1 \lor \neg x_3 \lor x_4) \land (\neg x_2 \lor x_3 \lor \neg x_4).</math>
The output of the problem is the value of the quantified expression. Finding this value is PSPACE-complete.{{r|garey-johnson}}

===Reconfiguration===
[[Reconfiguration]] problems concern the connectivity of a [[state space]] of solutions to a combinatorial problem. For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete,{{r|boncer}} even though the same problem for 3-colorings can be solved in polynomial time.{{r|jkkpp}} Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve [[nondeterministic constraint logic]], in which the states are [[Orientation (graph theory)|orientations]] of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.{{r|hearn-demaine}}

===Puzzles and games===
{{For|a list of games by completeness for PSPACE or other complexity classes|Game complexity}}
The quantified Boolean formula problem can be interpreted as a game by two players, a verifier and a falsifier. The players make moves that fill in values for the quantified variables, in the order they are nested, with the verifier filling in existentially quantified variables and the falsifier filling in universally quantified variables; the game is won by the verifier if the filled-in formula becomes true, and by the falsifier otherwise. A quantified formula is true if and only if the verifier has a winning strategy. Similarly, the problem of determining the winner or loser of many other [[combinatorial game theory|combinatorial games]] turns out to be PSPACE-complete. Examples of games that are PSPACE-complete (when [[generalized game|generalized]] so that they can be played on an <math>n\times n</math> board) are the games [[Hex (board game)|Hex]] and [[Reversi]].  Some other generalized games, such as [[chess]], [[English draughts|checkers]] (draughts), and [[Go (board game)|Go]] are [[EXPTIME-complete]] because a game between two perfect players can be very long, so they are unlikely to be in PSPACE. But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced.{{r|eppstein}}

It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems,{{r|hearn-demaine}} and include the solitaire games [[Rush Hour (board game)|Rush Hour]], [[Mahjong solitaire|Mahjong]], [[Atomix (computer game)|Atomix]] and [[Sokoban]], and the [[mechanical computer]] [[Turing Tumble]].{{r|eppstein}}

PSPACE-completeness is based on complexity as a function of the input size <math>n</math>, in the limit as <math>n</math> grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional <math>8\times 8</math> board cannot be PSPACE-complete, because they could be solved in constant time and space using a very large [[lookup table]]. To formulate PSPACE-complete versions of these games, they must be modified in a way that makes their number of positions unbounded, such as by playing them on an <math>n\times n</math> board instead. In some cases, such as for chess, these extensions are artificial.

==References==
{{reflist|refs=

<ref name=arora-barak>{{citation
 | last1 = Arora | first1 = Sanjeev
 | last2 = Barak | first2 = Boaz
 | isbn = 978-1-139-47736-9
 | page = 92
 | publisher = Cambridge University Press
 | title = Computational Complexity: A Modern Approach
 | url = https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA92
 | year = 2009}}</ref>

<ref name=berman-hartmanis>{{citation
 | last1 = Berman | first1 = L.
 | last2 = Hartmanis | first2 = J. | author2-link = Juris Hartmanis
 | doi = 10.1137/0206023
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 455536
 | pages = 305–322
 | title = On isomorphisms and density of NP and other complete sets
 | volume = 6
 | year = 1977| hdl = 1813/7101
 | hdl-access = free
 }}</ref>

<ref name=boncer>{{citation
 | last1 = Bonsma | first1 = Paul
 | last2 = Cereceda | first2 = Luis
 | doi = 10.1016/j.tcs.2009.08.023 | doi-access = free
 | issue = 50
 | journal = Theoretical Computer Science
 | mr = 2573973
 | pages = 5215–5226
 | title = Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
 | volume = 410
 | year = 2009}}</ref>

<ref name=eppstein>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | title = Computational Complexity of Games and Puzzles
 | url = http://www.ics.uci.edu/~eppstein/cgt/hard.html}}</ref>

<ref name=garey-johnson>{{citation
 | last1 = Garey | first1 = Michael R. | author1-link = Michael R. Garey
 | last2 = Johnson | first2 = David S. | author2-link = David S. Johnson
 | contribution = Section 7.4: Polynomial Space Completeness
 | isbn = 0-7167-1045-5
 | pages = [https://archive.org/details/computersintract0000gare/page/170 170–177]
 | publisher = W.H. Freeman
 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | year = 1979}}</ref>

<ref name=hearn-demaine>{{citation
 | last1 = Hearn | first1 = Robert A. | author1-link = Bob Hearn
 | last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine
 | publisher = [[A K Peters]]
 | title = Games, Puzzles, and Computation
 | title-link = Games, Puzzles, and Computation
 | year = 2009}}</ref>

<ref name=hitchcock-pavan>{{citation
 | last1 = Hitchcock | first1 = John M.
 | last2 = Pavan | first2 = Aduri
 | editor1-last = Chatterjee | editor1-first = Krishnendu
 | editor2-last = Sgall | editor2-first = Jirí
 | contribution = Length-increasing reductions for PSPACE-completeness
 | doi = 10.1007/978-3-642-40313-2_48
 | mr = 3126236
 | pages = 540–550
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings
 | volume = 8087
 | year = 2013}}</ref>

<ref name=hunt>{{citation
 | last = Hunt | first = Harry B. III
 | editor1-last = Aho | editor1-first = Alfred V.
 | editor2-last = Borodin | editor2-first = Allan
 | editor3-last = Constable | editor3-first = Robert L.
 | editor4-last = Floyd | editor4-first = Robert W.
 | editor5-last = Harrison | editor5-first = Michael A.
 | editor6-last = Karp | editor6-first = Richard M.
 | editor7-last = Strong | editor7-first = H. Raymond
 | contribution = On the time and tape complexity of languages, I
 | doi = 10.1145/800125.804030
|doi-access=free
|url=https://dl.acm.org/doi/pdf/10.1145/800125.804030
 | hdl = 1813/6007
 | pages = 10–19
 | publisher = Association for Computing Machinery
 | title = Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA
 | year = 1973| s2cid = 15937339
 | hdl-access = free
|url-status=live |archive-url=https://web.archive.org/web/20240117051807/https://dl.acm.org/doi/pdf/10.1145/800125.804030 |archive-date= Jan 17, 2024 
 }}</ref>

<ref name=jkkpp>{{citation
 | last1 = Johnson | first1 = Matthew
 | last2 = Kratsch | first2 = Dieter
 | last3 = Kratsch | first3 = Stefan
 | last4 = Patel | first4 = Viresh
 | last5 = Paulusma | first5 = Daniël
 | doi = 10.1007/s00453-015-0009-7
 | issue = 2
 | journal = Algorithmica
 | mr = 3506195
 | pages = 295–321
 | title = Finding shortest paths between graph colourings
 | volume = 75
 | year = 2016| s2cid = 6810123
 | url = http://dro.dur.ac.uk/15595/1/15595.pdf
 }}</ref>

<ref name=kuroda>{{citation
 | last = Kuroda | first = S.-Y. | author-link = S.-Y. Kuroda
 | doi = 10.1016/s0019-9958(64)90120-2 | doi-access = free
 | journal = Information and Computation
 | mr = 0169724
 | pages = 207–223
 | title = Classes of languages and linear-bounded automata
 | volume = 7
 | year = 1964| issue = 2 }}</ref>

<ref name=watanabe-tang>{{citation
 | last1 = Watanabe | first1 = Osamu
 | last2 = Tang | first2 = Shou Wen
 | doi = 10.1016/0304-3975(92)90074-P
 | issue = 2
 | journal = Theoretical Computer Science
 | mr = 1163815
 | pages = 199–215
 | title = On polynomial-time Turing and many-one completeness in PSPACE
 | volume = 97
 | year = 1992| doi-access = free
 }}</ref>

}}

==Further reading==
*{{citation
 | last = Sipser | first = Michael | author-link = Michael Sipser
 | contribution = Section 8.3: PSPACE-completeness
 | isbn = 0-534-94728-X
 | pages = [https://archive.org/details/introductiontoth00sips/page/283 283–294]
 | publisher = PWS Publishing
 | title = Introduction to the Theory of Computation
 | year = 1997
 | url = https://archive.org/details/introductiontoth00sips/page/283 | url-access = registration}}

{{ComplexityClasses}}

[[Category:Complexity classes]]