PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.
Problems known to be PSPACE-complete include determining properties of
Theory
A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem.[1]
The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P (polynomial time) and NP (non-deterministic polynomial time), but that is not known.[2] It is known that they lie outside of the class NC, a class of problems with highly efficient parallel algorithms, because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.
The transformations that are usually considered in defining PSPACE-completeness are polynomial-time many-one reductions, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using Turing reductions, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems.[3] Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.[4]
A version of the Berman–Hartmanis conjecture for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time bijections.[5]
Examples
Formal languages
Given a regular expression , determining whether it generates every string over its alphabet is PSPACE-complete.[6]
The first known PSPACE-complete problem was the
Logic
A standard PSPACE-complete problem, used in many other PSPACE-completeness results, is the
Reconfiguration
Puzzles and games
The quantified Boolean formula problem can be interpreted as a game by two players, a verifier and a falsifier. The players make moves that fill in values for the quantified variables, in the order they are nested, with the verifier filling in existentially quantified variables and the falsifier filling in universally quantified variables; the game is won by the verifier if the filled-in formula becomes true, and by the falsifier otherwise. A quantified formula is true if and only if the verifier has a winning strategy. Similarly, the problem of determining the winner or loser of many other combinatorial games turns out to be PSPACE-complete. Examples of games that are PSPACE-complete (when generalized so that they can be played on an board) are the games
It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems,
PSPACE-completeness is based on complexity as a function of the input size , in the limit as grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional board cannot be PSPACE-complete, because they could be solved in constant time and space using a very large lookup table. To formulate PSPACE-complete versions of these games, they must be modified in a way that makes their number of positions unbounded, such as by playing them on an board instead. In some cases, such as for chess, these extensions are artificial.
References
- ^ ISBN 0-7167-1045-5
- ISBN 978-1-139-47736-9
- MR 1163815
- MR 3126236
- MR 0455536
- from the original on Jan 17, 2024
- MR 0169724
- MR 2573973
- S2CID 6810123
- ^ a b Hearn, Robert A.; Demaine, Erik D. (2009), Games, Puzzles, and Computation, A K Peters
- ^ a b Eppstein, David, Computational Complexity of Games and Puzzles
Further reading
- ISBN 0-534-94728-X