In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2^p(n)) time, where p(n) is a polynomial function of n. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... It has been suggested that Landau notation be merged into this article or section. ...

In terms of DTIME, In computational complexity theory, the complexity class DTIME(f(n)) or TIME(f(n)) is the set of decision problems that can be solved by a deterministic Turing machine using time O(f(n)), and unlimited space. ...

We know

P NP PSPACE EXPTIME NEXPTIME EXPSPACE

and also, by the time hierarchy theorem, In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain hard problems which cannot be solved in a given amount of time. ...

P EXPTIME   (equivalently, P ≠ EXPTIME)

so at least one of the first three inclusions on the first line must be proper (most experts believe all the inclusions are proper). It's also known that if P = NP, then EXPTIME = NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine.¹ In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ... In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of...

EXPTIME can also be reformulated as the space class APSPACE, the 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.² In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The definition of NP uses the existential mode of computation: if any choice leads...

EXPTIME-complete

The complexity class EXPTIME-complete is also a set of decision problems. A decision problem is in 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 is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPTIME-complete might be thought of as the hardest problems in EXPTIME. Notice that although we don't know if NP-complete is a subset of P or not, we do know that EXPTIME-complete lies outside P; none of these problems can possibly be solved in polynomial time. In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ... Flowcharts are often used to represent algorithms. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

In computability theory, one of the basic undecidable problems is that of deciding whether a deterministic Turing machine (DTM) accepts a particular input. One of the most fundamental EXPTIME-complete problems is a simpler version of this which asks if a DTM accepts an input in at most k steps. It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits.⁴ 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. Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

Other examples of EXPTIME-complete problems include the problem of looking at a generalized Chess, Checkers, or Go position, and determining whether the first player can force a win. These games are EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. By contrast, generalized games that can last for a number of moves that is polynomial in the size of the board are often PSPACE-complete. In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. ... Listen to this article · (info) This audio file was created from an article revision dated 2006-03-08, and does not reflect subsequent edits to the article. ... starting position on a 10×10 draughts board Draughts, also known as checkers, is a group of mental sport board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemys pieces. ... Go, also known as Weiqi or Baduk, is a strategic, two-player board game originating in ancient China between 2000 BC and 200 BC. The game is now popular throughout East Asia. ... In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. ... In complexity theory, PSPACE-complete is a complexity class. ...

Another set of important EXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an adjacency matrix, is P-complete, then solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller.³ In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n × n matrix where the nondiagonal entry aij is the number of edges joining vertex and vertex , and the diagonal entry aii is either twice the number of loops at vertex or just... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ...

See also

• Game complexity

In combinatorial game theory, game complexity is a measure of the complexity of a game. ...

External links

• Scott Aaronson's Complexity Zoo

References

C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0201530821. Section 20.1: Exponential time, pp. 491–499.

Chris Umans. CS 21: Lecture 13 notes.

Footnotes

1. Papadimitriou, section 20.1, pg.491.

2. Papadimitriou, section 20.1, Corollary 3, pg.495.

3. Papadimitriou, section 20.1, pg.492.

4. Umans, slide 24.