List of PSPACE-complete problems

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:

Amazons Atomix Checkers if a draw is forced after a polynomial number of non-jump moves Dyson Telescope Game Cross Purposes Geography Two-player game version of Instant Insanity Ko-free Go Ladder capturing in GoGo ladders are PSPACE-complete Gomoku Hex Konane Lemmings Node Kayles Poset Game Reversi River Crossing Rush Hour Finding optimal play in Mahjong solitaireA. 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. Scrabble Sokoban Super Mario Bros.Lay summary: Black Pebble gameGilbert, 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. Black-White Pebble gamePhilipp Hertel and Toniann Pitassi: Black-White Pebbling is PSPACE-Complete Acyclic pebble gameTakumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems, SIAM Journal on Computing, Volume 8, 1979, pages 574-586. One-player pebble game Token on acyclic directed graph games

Logic

Quantified boolean formulas

First-order logic of equalityK. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986. Provability in intuitionistic propositional logic Satisfaction in modal logic S4 First-order theory of the natural numbers under the successor operation First-order theory of the natural numbers under the standard order First-order theory of the integers under the standard order First-order theory of well-ordered sets First-order theory of binary strings under lexicographic ordering First-order theory of a finite Boolean algebra Stochastic satisfiability Linear temporal logic satisfiability and model checking

Lambda calculus Type inhabitation problem for simply typed lambda calculus

Automata and language theory

Circuit theory Integer circuit evaluationInteger circuit evaluation

Automata theory

Word problem for linear bounded automata Word problem for quasi-realtime automata Emptiness problem for a nondeterministic two-way finite state automatonGalil, Z. Hierarchies of Complete Problems. In Acta Informatica 6 (1976), 77-88. Equivalence problem for nondeterministic finite automataL. 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. Word problem and emptiness problem for non-erasing stack automataJ. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, first edition, 1979. Emptiness of intersection of an unbounded number of deterministic finite automataD. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.

A generalized version of Langton's AntLangton's Ant problem , "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) Minimizing nondeterministic finite automataT. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.

Formal languages

Word problem for context-sensitive languageS.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964. Intersection emptiness for an unbounded number of regular languages Regular Expression Star-Freeness Equivalence problem for regular expressions Emptiness problem for regular expressions with intersection. Equivalence problem for star-free regular expressions with squaring. Covering for linear grammars Structural equivalence for linear grammars Equivalence problem for Regular grammars Emptiness problem for ET0L grammars Word problem for ET0L grammars Tree transducer language membership problem for top down finite-state tree transducers

Graph theory

Succinct versions of many graph problems, with graphs represented as Boolean circuits,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. ordered binary decision diagramsJ. 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. 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 Canadian traveller problem. Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferencesAlex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond . In SODA 2008. Deterministic constraint logic (unbounded) Dynamic graph reliability. Graph coloring game Node Kayles game and clique-forming game: 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)

Others

Finite horizon POMDPs (Partially Observable Markov Decision Processes). Hidden Model MDPs (hmMDPs). Dynamic Markov process. Detection of inclusion dependencies in a relational database Computation of any Nash equilibrium of a 2-player normal-form game, that may be obtained via the Lemke–Howson algorithm. 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 ?

List of PSPACE-complete problems

Bron en licentie