EXPTIME

from Wikipedia, the free encyclopedia
Relation to other complexity classes

In complexity theory , EXPTIME (sometimes just EXP ) stands for the complexity class of decision problems that can be decided by a deterministic Turing machine (DTM) in a limited time . is any polynomial in the input length . In the DTIME therefore expressed notation applies:

EXPTIME completeness

A problem is EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME can be traced back to this in polynomial time ( polynomial time reduction ). While the question of the equality of P and NP is a famous open problem in computer science ( P-NP problem , especially whether NP-complete problems lie in P), EXPTIME-complete problems are known to be not in P. This also follows from the time hierarchy theorem .

An example is a variant of the holding problem for deterministic Turing machines, to decide whether this holds in at most k steps for a given input. The language is an example of an EXPTIME-complete language and the halting problem mentioned corresponds to the word problem in that language. The reason for the EXPTIME difficulty is intuitively that the number is exponentially greater than the length of its coding ( bits), and there is generally no more efficient way of deciding whether to stop after at most steps than to open for steps simulate.

Examples of EXPTIME complete problems

Several examples of EXPTIME-complete problems are two-person games. The specific question is whether a player from a given playing position has a strategy to safely win the game. Examples of EXPTIME-complete games are

  • generalized chess (on an nxn board for arbitrarily high n, the required time grows exponentially with n)
  • lady
  • Go with the Japanese knockout rules

All of these games have in common that a game can have an exponential number of moves. Games that only allow many polynomial moves per game and in which a game position is described polynomially can be solved in PSPACE .

Another source of EXPTIME-complete are graph problems, where the input is represented by a compact circuit. This circuit can be exponentially smaller than an explicit representation of the graph. Since the complexity is given in relation to the input size, many problems that are complete with an explicit representation P -complete are complete with the circuit representation EXPTIME.

Relationship to other complexity classes

The following relationships are known:

NC P NP PSPACE EXPTIME NEXPTIME

Since P is a real subset of EXPTIME according to the time hierarchy record , at least one subset relationship P NP PSPACE EXPTIME must be real. It is believed that all inclusions are real.

Individual evidence

  1. Chris Umans: CS21: Decidability and Tractability, Lecture 18 (PDF; 133 kB)
  2. Aviezri Fraenkel, D. Lichtenstein, Computing a perfect strategy for n × n chess requires time exponential in n, J. Comb. Th. A, Vol. 31, 1981, pp. 199-214.
  3. ^ JM Robson, N by N checkers is Exptime complete, SIAM Journal on Computing, Volume 13, 1984, pp. 252-267
  4. JM Robson, The complexity of Go, Information Processing; Proceedings of IFIP Congress. 1983, pp. 413-417.
  5. Christos H. Papadimitriou: A Glimpse Beyond . In: Computational Complexity 1995, pp. 491-508.
  6. José L. Balcázar, Antoni Lozano, Jacobo Torán: The complexity of algorithmic problems on succinct instances. . In: Computer Science . 1992. doi : 10.1007 / 978-1-4615-3422-8_30 .

Web links

  • EXPTIME . In: Complexity Zoo. (English)