PSPACE-complete

Last updated

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.

Contents

Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.

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 word problem for deterministic context-sensitive grammars. In the word problem for context-sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and Kuroda (1964) showed that every (possibly non-deterministic) program computable in linear space could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism. [7] In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE. [1]

Logic

A standard PSPACE-complete problem, used in many other PSPACE-completeness results, is the quantified Boolean formula problem, a generalization of the Boolean satisfiability problem. The quantified Boolean formula problem takes as input a Boolean expression, with all of its variables quantified either universally or existentially, for example: The output of the problem is the value of the quantified expression. Finding this value is PSPACE-complete. [1]

Reconfiguration

Reconfiguration problems concern the connectivity of a state space of solutions to a combinatorial problem. For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete, [8] even though the same problem for 3-colorings can be solved in polynomial time. [9] Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve nondeterministic constraint logic, in which the states are orientations of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge. [10]

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 Hex and Reversi. Some other generalized games, such as chess, checkers (draughts), and Go are EXPTIME-complete because a game between two perfect players can be very long, so they are unlikely to be in PSPACE. But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced. [11]

It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems, [10] and include the solitaire games Rush Hour, Mahjong, Atomix and Sokoban, and the mechanical computer Turing Tumble. [11]

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.

Related Research Articles

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

<span class="mw-page-title-main">NP-hardness</span> Complexity class

In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H. That is, assuming a solution for H takes 1 unit time, H's solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class NP. As it is suspected, but unproven, that P≠NP, it is unlikely that any polynomial-time algorithms for NP-hard problems exist.

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

<span class="mw-page-title-main">PP (complexity)</span> Class of problems in computer science

In complexity theory, PP, or PPT is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time .

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981.

In computational complexity theory, NL is the complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.

<span class="mw-page-title-main">IP (complexity)</span>

In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not relativize.

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

References

  1. 1 2 3 Garey, Michael R.; Johnson, David S. (1979), "Section 7.4: Polynomial Space Completeness", Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, pp.  170–177, ISBN   0-7167-1045-5
  2. Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, p. 92, ISBN   978-1-139-47736-9
  3. Watanabe, Osamu; Tang, Shou Wen (1992), "On polynomial-time Turing and many-one completeness in PSPACE", Theoretical Computer Science, 97 (2): 199–215, doi: 10.1016/0304-3975(92)90074-P , MR   1163815
  4. Hitchcock, John M.; Pavan, Aduri (2013), "Length-increasing reductions for PSPACE-completeness", in Chatterjee, Krishnendu; Sgall, Jirí (eds.), Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings, Lecture Notes in Computer Science, vol. 8087, Springer, pp. 540–550, doi:10.1007/978-3-642-40313-2_48, MR   3126236
  5. Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing , 6 (2): 305–322, doi:10.1137/0206023, hdl: 1813/7101 , MR   0455536
  6. Hunt, Harry B. III (1973), "On the time and tape complexity of languages, I", in Aho, Alfred V.; Borodin, Allan; Constable, Robert L.; Floyd, Robert W.; Harrison, Michael A.; Karp, Richard M.; Strong, H. Raymond (eds.), Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, Association for Computing Machinery, pp. 10–19, doi: 10.1145/800125.804030 , hdl: 1813/6007 , S2CID   15937339, archived from the original on Jan 17, 2024
  7. Kuroda, S.-Y. (1964), "Classes of languages and linear-bounded automata", Information and Computation, 7 (2): 207–223, doi: 10.1016/s0019-9958(64)90120-2 , MR   0169724
  8. Bonsma, Paul; Cereceda, Luis (2009), "Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances", Theoretical Computer Science, 410 (50): 5215–5226, doi: 10.1016/j.tcs.2009.08.023 , MR   2573973
  9. Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël (2016), "Finding shortest paths between graph colourings" (PDF), Algorithmica, 75 (2): 295–321, doi:10.1007/s00453-015-0009-7, MR   3506195, S2CID   6810123
  10. 1 2 Hearn, Robert A.; Demaine, Erik D. (2009), Games, Puzzles, and Computation, A K Peters
  11. 1 2 Eppstein, David, Computational Complexity of Games and Puzzles

Further reading