List of PSPACE-complete problems

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· Geography· Gomoku· Hex· Reversi· Rush Hour· Finding optimal play in Mahjong solitaire· Sokoban· Pebble game [Philipp Hertel and Toniann Pitassi: [http://www.cs.toronto.edu/~philipp/pages/papers/BWPebbling.pdf Black-White Pebbling is PSPACE-Complete] ]
* Ladder capturing in Go

Logic

Quantified boolean formulas· Nondetermistic constraint logic· First-order logic of equality· Satisfaction in intuitionistic propositional logic· Satisfaction in modal logic S4· Nondetermistic constraint logic· 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 setFirst-order theory of binary strings under lexicographic ordering· First-order theory of a finite Boolean algebra

Lambda calculus

Type inhabitation problem

Automata and language theory

Circuit theory

Integer circuit evaluation

Automata theory

Word problem for linear bounded automata· Two-way finite state automaton non-emptinessFact|date=October 2008· Equivalence problem for nondeterministic finite automata [ L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. InProceedings of the 5th Symposium on Theory of Computing, pages 1–9, 1973.] · Word problem and emptiness problem for non-erasing stack automata [ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, second edition, 1979.] · Regular expression star freeness [ [http://www.inf.u-szeged.hu/actacybernetica/vol13n1/cikk1.xml Regular expression star-freeness is PSPACE-complete] ] · Quasi-realtime automaton acceptance?· Deterministic finite automata intersection emptiness [D. 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 Ant [ [http://sciencelinks.jp/j-east/article/200212/000020021202A0428168.php Langton'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 automata [T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal onComputing, 22(6):1117–1141, December 1993.]

Formal languages

Context-sensitive language membership· Regular language intersection [D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.] [M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.] [K.-J. Lange and P. Rossmanith. The emptiness problem for intersections of regular languages. In I. Havel, editor, Proc. of the 17th Conf. on Mathematical Foundations of Computer Science, number 629 in LNCS, pages 346–354. Springer-Verlag, 1992.]

Networking

* Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences [Alex Fabrikant and Christos Papadimitriou. [http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond] . In SODA 2008.]

See also

* List of NP-complete problems

References

* Wagner, K and Wechsung, G. Computational Complexity. D Reidel Publishing Company, 1986. ISBN 90-277-2146-7
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Eppstein's page on computational complexity of games]
* [http://arxiv.org/abs/cs.CC/0205005 Nondeterministic Constraint Logic]
* [http://arxiv.org/abs/cs.CC/9409225 The Complexity of Approximating PSPACE-complete problems]
* [http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6911/18589/00856751.pdf Integer circuit evaluation]
* [http://homepages.cwi.nl/~tromp/lad.ps Go ladders are PSPACE-complete]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • PSPACE-complete — Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE complete is one of these types.Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the… …   Wikipedia

  • List of problems — *List of undecidable problems *List of unsolved problems *List of open problems in computer science *List of NP complete problems *List of PSPACE complete problems *List of problems solved by MacGyver …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… …   Wikipedia

  • P-complete — In complexity theory, the notion of P complete decision problems is useful in the analysis of both: which problems are difficult to parallelize effectively, and; which problems are difficult to solve in limited space. Formally, a decision problem …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia

  • Game complexity — Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state space complexity, game tree size, decision complexity, game tree complexity, and computational complexity. Contents 1 Measures of… …   Wikipedia

  • P = NP problem — The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”