List of PSPACE-complete problems
Jump to navigation
Jump to search
Template:Short description Script error: No such module "Hatnote". Template:Use mdy dates
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:
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- Amazons[1]
- Atomix[2]
- Checkers if a draw is forced after a polynomial number of non-jump moves[3]
- Dyson Telescope Game[4]
- Cross Purposes[5]
- Geography
- Two-player game version of Instant Insanity
- Ko-free Go[6]
- Ladder capturing in Go[7]
- Gomoku[8]
- Hex[9]
- Konane[5]
- Lemmings[10]
- Node Kayles[11]
- Poset Game[12]
- Reversi[13]
- River Crossing[14]
- Rush Hour[14]
- Finding optimal play in Mahjong solitaire[15]
- Scrabble[16]
- Sokoban[14]
- Super Mario Bros.[17]
- Black Pebble game[18]
- Black-White Pebble game[19]
- Acyclic pebble game[20]
- One-player pebble game[20]
- Token on acyclic directed graph games:[11]
Logic
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- Quantified boolean formulas
- First-order logic of equality[21]
- Provability in intuitionistic propositional logic
- Satisfaction in modal logic S4[21]
- First-order theory of the natural numbers under the successor operation[21]
- First-order theory of the natural numbers under the standard order[21]
- First-order theory of the integers under the standard order[21]
- First-order theory of well-ordered sets[21]
- First-order theory of binary strings under lexicographic ordering[21]
- First-order theory of a finite Boolean algebra[21]
- Stochastic satisfiability[22]
- Linear temporal logic satisfiability and model checking[23]
Lambda calculus
Type inhabitation problem for simply typed lambda calculus
Automata and language theory
Circuit theory
Integer circuit evaluation[24]
Automata theory
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- Word problem for linear bounded automataTemplate:Sfnp
- Word problem for quasi-realtime automataTemplate:Sfnp
- Emptiness problem for a nondeterministic two-way finite state automatonTemplate:Sfnp[25]
- Equivalence problem for nondeterministic finite automataTemplate:Sfnp[26]
- Word problem and emptiness problem for non-erasing stack automata[27]
- Emptiness of intersection of an unbounded number of deterministic finite automata[28]
- A generalized version of Langton's Ant[29]
- Minimizing nondeterministic finite automata[30]
Formal languages
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- Word problem for context-sensitive language[31]
- Intersection emptiness for an unbounded number of regular languages [28]
- Regular Expression Star-Freeness [32]
- Equivalence problem for regular expressions[21]
- Emptiness problem for regular expressions with intersection.[21]
- Equivalence problem for star-free regular expressions with squaring.[21]
- Covering for linear grammarsTemplate:Sfnp
- Structural equivalence for linear grammarsTemplate:Sfnp
- Equivalence problem for Regular grammarsTemplate:Sfnp
- Emptiness problem for ET0L grammarsTemplate:Sfnp
- Word problem for ET0L grammarsTemplate:Sfnp
- Tree transducer language membership problem for top down finite-state tree transducersTemplate:Sfnp
Graph theory
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- succinct versions of many graph problems, with graphs represented as Boolean circuits,[33] ordered binary decision diagrams[34] or other related representations:
- s-t reachability problem for succinct graphs. This is essentially the same as the simplest plan existence problem in automated planning and scheduling.
- planarity of succinct graphs
- acyclicity of succinct graphs
- connectedness of succinct graphs
- existence of Eulerian paths in a succinct graph
- Bounded two-player Constraint Logic[11]
- Canadian traveller problem.[35]
- Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences[36]
- Deterministic constraint logic (unbounded)[37]
- Dynamic graph reliability.[22]
- Graph coloring game[38]
- Node Kayles game and clique-forming game:[39] two players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins.
- Nondeterministic Constraint Logic (unbounded)[11]
Others
<templatestyles src="Div col/styles.css"/>
Script error: No such module "Check for unknown parameters".
- Finite horizon POMDPs (Partially Observable Markov Decision Processes).[40]
- Hidden Model MDPs (hmMDPs).[41]
- Dynamic Markov process.[22]
- Detection of inclusion dependencies in a relational database[42]
- Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm.[43]
- 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 ?[44][45]
See also
Notes
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ a b Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Go ladders are PSPACE-complete Template:Webarchive
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ a b c d Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ a b c Script error: No such module "citation/CS1".
- ↑ A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM Journal on Computing 26:2 (1997) 369-400.
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
Lay summary: Script error: No such module "citation/CS1". - ↑ Gilbert, Lengauer, and R. E. Tarjan: The Pebbling Problem is Complete in Polynomial Space. SIAM Journal on Computing, Volume 9, Issue 3, 1980, pages 513-524.
- ↑ Philipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Template:Webarchive
- ↑ a b Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
- ↑ a b c d e f g h i j k K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. Template:Isbn
- ↑ a b c Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Integer circuit evaluation
- ↑ Galil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88.
- ↑ L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973.
- ↑ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979.
- ↑ a b D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
- ↑ Langton's Ant problem Template:Webarchive, "Generalized symmetrical Langton's ant problem is PSPACE-complete" by YAMAGUCHI EIJI and TSUKIJI TATSUIE in IEIC Technical Report (Institute of Electronics, Information and Communication Engineers)
- ↑ T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.
- ↑ S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
- ↑ Script error: No such module "citation/CS1".
- ↑ Antonio Lozano and Jose L. Balcazar. The complexity of graph problems for succinctly represented graphs. In Manfred Nagl, editor, Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG'89, number 411 in Lecture Notes in Computer Science, pages 277–286. Springer-Verlag, 1990.
- ↑ J. Feigenbaum and S. Kannan and M. Y. Vardi and M. Viswanathan, Complexity of Problems on Graphs Represented as OBDDs, Chicago Journal of Theoretical Computer Science, vol 5, no 5, 1999.
- ↑ Script error: No such module "citation/CS1".
- ↑ Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond Template:Webarchive. In SODA 2008.
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
References
- Script error: No such module "citation/CS1".
- Eppstein's page on computational complexity of games
- The Complexity of Approximating PSPACE-complete problems for hierarchical specifications