Examples PSPACE-complete

1 examples

1.1 regular expressions , automata
1.2 context-sensitive grammars
1.3 quantified boolean formulas
1.4 puzzles , games

examples

below descriptions of few pspace-complete problems. more examples can found @ list of pspace-complete problems.

regular expressions , automata

given regular expression r, determining whether generates every string on alphabet pspace-complete.

a related result class of languages recognizable 0 error automata two-way infinite random tape equals nondeterministic linear space. holds both two-way , multipass one-way access input. testing whether automaton (with two-way infinite random tape) accepts word 0 error nspace(o(kn)) complete, n input size , k number of states.

context-sensitive grammars

the first known pspace-complete problem word problem deterministic context-sensitive grammars. in word problem context-sensitive grammars, 1 given set of grammatical transformations can increase, cannot decrease, length of sentence, , wishes determine if given sentence produced these transformations. technical condition of determinism (implying each transformation makes obvious used) ensures process can solved in polynomial space, , kuroda (1964) showed every (possibly non-deterministic) program computable in linear space converted parsing of context-sensitive grammar, in way preserves determinism. in 1970, savitch s theorem showed pspace closed under nondeterminism, implying non-deterministic context-sensitive grammars in pspace.

quantified boolean formulas

nowadays, archetypal pspace-complete problem taken quantified boolean formula problem (usually abbreviated qbf or tqbf; t stands true ), generalization of first known np-complete problem, boolean satisfiability problem (sat). satisfiability problem problem of whether there assignments of truth values variables make boolean expression true. example, 1 instance of sat question of whether following true:

∃

x

1



∃

x

2



∃

x

3



∃

x

4


:
(

x

1


∨
¬

x

3


∨

x

4


)
∧
(
¬

x

2


∨

x

3


∨
¬

x

4


)


{\displaystyle \exists x_{1}\,\exists x_{2}\,\exists x_{3}\,\exists x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4})}

the quantified boolean formula problem differs in allowing both universal , existential quantification on values of variables:

∃

x

1



∀

x

2



∃

x

3



∀

x

4


:
(

x

1


∨
¬

x

3


∨

x

4


)
∧
(
¬

x

2


∨

x

3


∨
¬

x

4


)


{\displaystyle \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})}

.

the proof qbf pspace-complete problem restatement of proof of savitch s theorem in language of logic, , bit more technical.

puzzles , games

the np-complete problem in previous section resembles typical puzzles: there way plug in values solves problem? correspondingly, pspace-complete problem there resembles games: there move can make, such moves opponent might make, there move can make win? question alternates existential , universal quantifiers. not surprisingly, many puzzles turn out np-complete, , many games turn out pspace-complete.

examples of games pspace-complete (when generalized can played on n × n board) games hex , reversi , solitaire games rush hour, mahjong, atomix, , sokoban. other generalized games, such chess, checkers (draughts), , go exptime-complete because game between 2 perfect players can long, unlikely in pspace. become pspace-complete if polynomial bound on number of moves enforced.

note definition of pspace-completeness based on asymptotic complexity: time takes solve problem of size n, in limit n grows without bound. means finite game checkers (which played on 8 × 8 board) never pspace-complete, since can solved in constant time , space using large lookup table (checkers solved in way). why games modified playing them on n × n board instead; in cases, such chess, these extensions artificial , subjective.

see game complexity more games completeness pspace or other complexity classes has been determined.