Misplaced Pages

#855144

32-501: EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. EXPTIME relates to

64-490: A Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle ) and Σ 0 E = E {\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}} . One also defines An equivalent definition is that a language L is in Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} if and only if it can be written in

96-629: A Σ k − 1 P {\displaystyle \Sigma _{k-1}^{\mathsf {P}}} oracle), Σ 0 E X P = E X P {\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}} , and again: A language L is in Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} if and only if it can be written as where R ( x , y 1 , … , y k ) {\displaystyle R(x,y_{1},\ldots ,y_{k})}

128-475: 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

160-419: A number of moves that is polynomial in the size of the board are often PSPACE-complete . The same is true of exponentially long games in which non-repetition is automatic. Another set of important EXPTIME-complete problems relates to succinct circuits . Succinct circuits are simple machines used to describe some graphs in exponentially less space. They accept two vertex numbers as input and output whether there

192-452: 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. 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. It is known that they lie outside of

224-482: 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. Other types of reductions, such as many-one reductions that always increase

256-456: 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 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. A problem is defined to be PSPACE-complete if it can be solved using

288-501: Is PSPACE-complete. 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

320-457: Is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. Problems that are EXPTIME-complete might be thought of as the hardest problems in EXPTIME. Notice that although it is unknown whether NP is equal to P, we do know that EXPTIME-complete problems are not in P; it has been proven that these problems cannot be solved in polynomial time , by

352-457: Is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such as an adjacency matrix , solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs. Exponential hierarchy In computational complexity theory ,

SECTION 10

#1732782696856

384-499: Is computable in time 2 | x | c {\displaystyle 2^{|x|^{c}}} for some c , which again implicitly bounds the length of y i . Equivalently, EXPH is the class of languages computable in time 2 n c {\displaystyle 2^{n^{c}}} on an alternating Turing machine with constantly many alternations. Complexity Zoo : Class EH PSPACE-complete In computational complexity theory ,

416-879: 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: ∃ x 1 ∀ x 2 ∃ x 3 ∀ x 4 : ( x 1 ∨ ¬ x 3 ∨ x 4 ) ∧ ( ¬ x 2 ∨ x 3 ∨ ¬ x 4 ) . {\displaystyle \exists x_{1}\,\forall x_{2}\,\exists x_{3}\,\forall x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4}).} The output of

448-565: Is the union of the classes Σ k E X P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}} , where Σ k E X P = N E X P Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}} (languages computable in nondeterministic time 2 n c {\displaystyle 2^{n^{c}}} for some constant c with

480-472: The exponential hierarchy is a hierarchy of complexity classes that is an exponential time analogue of the polynomial hierarchy . As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds 2 c n {\displaystyle 2^{cn}} for a constant c , and full exponential bounds 2 n c {\displaystyle 2^{n^{c}}} ), leading to two versions of

512-406: The time hierarchy theorem . In computability theory , one of the basic undecidable problems is the halting problem : deciding whether a deterministic Turing machine (DTM) halts. One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts on a given input in at most k steps. It is in EXPTIME because a trivial simulation requires O( k ) time, and

544-588: The above expressions, the symbol ⊆ means "is a subset of", and the symbol ⊊ means "is a strict subset of". so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are. It is also known that if P = NP , then EXPTIME = NEXPTIME , the class of problems solvable in exponential time by a nondeterministic Turing machine . More precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P . EXPTIME can be reformulated as

576-520: 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

608-738: The exponential hierarchy. This hierarchy is sometimes also referred to as the weak exponential hierarchy, to differentiate it from the strong exponential hierarchy. The complexity class EH is the union of the classes Σ k E {\displaystyle \Sigma _{k}^{\mathsf {E}}} for all k , where Σ k E = N E Σ k − 1 P {\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}} (i.e., languages computable in nondeterministic time 2 c n {\displaystyle 2^{cn}} for some constant c with

640-563: The form where R ( x , y 1 , … , y n ) {\displaystyle R(x,y_{1},\ldots ,y_{n})} is a predicate computable in time 2 c | x | {\displaystyle 2^{c|x|}} (which implicitly bounds the length of y i ). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time 2 c n {\displaystyle 2^{cn}} for some c with constantly many alternations. EXPH

672-489: 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 n × n {\displaystyle n\times n} board) are

SECTION 20

#1732782696856

704-484: 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. It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems, and include

736-406: The input k is encoded using O(log k ) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more. The same problem with the number of steps written in unary is P-complete . Other examples of EXPTIME-complete problems include

768-472: The length of the transformed input, have also been considered. 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 . Given a regular expression R {\displaystyle R} , determining whether it generates every string over its alphabet

800-416: The moves from state to state reverse the orientation of a single edge. 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;

832-408: The other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Furthermore, by the time hierarchy theorem and the space hierarchy theorem , it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE. In terms of DTIME , It is known that and also, by the time hierarchy theorem and the space hierarchy theorem , that In

864-430: The problem is the value of the quantified expression. Finding this value is PSPACE-complete. 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, even though

896-673: The problem of evaluating a position in generalized chess , checkers , or Go (with Japanese ko rules). These games have a chance of being EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is known to imply EXPTIME-completeness, but it is not known if the American or Chinese rules for the game are EXPTIME-complete (they could range from PSPACE to EXPSPACE). By contrast, generalized games that can last for

928-447: The same problem for 3-colorings can be solved in polynomial time. 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

960-573: The solitaire games Rush Hour , Mahjong , Atomix and Sokoban , and the mechanical computer Turing Tumble . PSPACE-completeness is based on complexity as a function of the input size n {\displaystyle n} , in the limit as n {\displaystyle n} grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional 8 × 8 {\displaystyle 8\times 8} board cannot be PSPACE-complete, because they could be solved in constant time and space using

992-432: The space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. This is one way to see that PSPACE ⊆ EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine. A decision problem is EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there

EXPTIME - Misplaced Pages Continue

1024-527: 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. In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE. A standard PSPACE-complete problem, used in many other PSPACE-completeness results,

#855144