EXPTIME

In computational complexity theory, the complexity class EXPTIME (also called EXP) is the set of decision problems that can be solved on a computing machine. Turing-time deterministic O(2^p(n)), where p(n) is a polynomial function over n.

In terms of DTIME,

EXPTIME= k한 한 NDTIME(2nk).{displaystyle {mbox{EXPTIME}=bigcup _{kin mathbb {N}}}{mbox{DTIME}}}left(2^{n^{k}}{right). !

It is known that

P N NP PSPACE EXPTIME EXPSPACE

and by the temporal hierarchy theorem:

P EXPTIME

so at least one of the first line includes must be strict (all such includes are thought to be strict).

The complexity class EXPTIME-complete is the set of decision problems that are in EXPTIME such that every EXPTIME problem has a polynomial transformation to every EXPTIME-complete problem. In other words, there is an algorithm that works in polynomial time that transforms the instances of one problem into the instances of another with the same answer. The EXPTIME-complete set can be seen as the set of the most difficult EXPTIME problems.

Examples of EXPTIME-complete problems are searching from a position (in a generalized version) of Chess, Checkers, or Go and determining if the first player has a winning sequence of moves from there. These games are EXPTIME-complete since the sequence of moves from a given configuration is exponential over the size of the board. (When you have a generalized game in which the number of moves from a configuration is polynomial in board size, the same problem is generally PSPACE-complete.)

EXPTIME-full

A decision problem is EXPTIME-complete if it is in EXPTIME, and all EXPTIME problems have polynomial-time, or a reduction thereof. In other words, there is a polynomial time algorithm that transforms instances of one to instances of the other with the same response. You might think that the problems that are EXPTIME-complete are the hardest problems in EXPTIME. Note that although we don't know whether NP is a subset of P or not, we do know that EXPTIME-complete problems are not in P; It has been shown that these problems cannot be solved in polynomial time.

In computability theory, one of the basic undecidable problems is deciding whether a deterministic Turing machine (DTM) stops (stopping problem). One of the more fundamental EXPTIME-complete problems is a simpler version of it, which tells whether a DTM stops in at most k steps. It is in EXPTIME because obviously a simulation takes O(k) time, and the input k is encoded by O(log k) bits. It is EXPTIME-complete, since we can use it to determine if a machine solving an EXPTIME problem exponentially accepts the number of steps; won't use anymore.

Other examples of EXPTIME-complete problems include the problem of evaluating a generalized situation in chess, checkers, or Go (with the Japanese ko rules). These games can be EXPTIME-complete because the games can last for a series of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is intractable enough to imply EXPTIME-full, but it is not known whether more flexible ones like the American or Chinese ones are EXPTIME-full.

In contrast, generalized games that can last a series of moves that are polynomial in board size are often PSPACE-complete.