List of PSPACE-complete problems

From Wikipedia, the free encyclopedia

Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive.

Games and puzzles

Generalized versions of:

Logic

Lambda calculus

Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Summarize
Perspective

Circuit theory

Integer circuit evaluation[24]

Automata theory

Formal languages

Graph theory

Others

  • Finite horizon POMDPs (Partially Observable Markov Decision Processes).[50]
  • Hidden Model MDPs (hmMDPs).[51]
  • Dynamic Markov process.[22]
  • Detection of inclusion dependencies in a relational database[52]
  • Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.[53]
  • The Corridor Tiling Problem: given a set of Wang tiles, a chosen tile and a width given in unary notation, is there any height such that an rectangle can be tiled such that all the border tiles are ?[54][55]

See also

Notes

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.