| • Science | • People | • Locations | • Timeline |
In terms of DTIME,
We know
and also, by the time hierarchy theorem,
so at least one of the 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. 1
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. 2
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-completeIn 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 th 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.
Examples of EXPTIME-complete problems include the problem of looking at a generalizedIn 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. For example, generalized chess is the game of chess played on an n by n board, with 2''n pieces on each side. Compl ChessFor other meanings, see Chess (disambiguation). Chess (from the Persian word Shah is a board game for two players played on a square board divided into eight rows (or ranks and eight columns (or files creating 64 individual squares which alternate in colo, CheckersThis article deals with the game of checkers. Checkers is also the name of a Cocker Spaniel after whom Richard Nixon's renowned Checkers speech was named. Checkers is also the name of an American fast-food restaurant chain; see Checkers Drive-In. This art, or GoGo is a strategic, two-player board game originating in ancient China between 2000 BC and 200 BC. Go is a popular game in East Asia. The development of Internet play has served to increase notably its popularity throughout the rest of the world, in recent 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 gameIn 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. For example, generalized chess is the game of chess played on an n by n board, with 2''n pieces on each side. Compls that can last for a number of moves that is polynomial in the size of the board are often PSPACE-completeIn complexity theory, PSPACE-complete is a complexity class. A decision problem is in PSPACE-complete if it is in PSPACE, and every problem in PSPACE can be reduced to it in polynomial time. The problems in PSPACE-complete can be thought of as the hardest.)
Another set of important EXPTIME-complete problems relates to succinct circuit s. 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-completeIn 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. A decision problem is in P-complete if it is in P, and every problem in P, then solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller. 3