ExpTime

EXPTIME, or EXP, is a standard complexity class in computational complexity theory. It consists of decision problems that can be solved by a deterministic Turing machine in time bounded by a function of the form 2^{p(n)}, where p is a polynomial and n is the input length. Equivalently, EXPTIME = ⋃_{k≥1} DTIME(2^{n^k}).

This class captures problems solvable in exponential time on a deterministic computer. Because a polynomial-time nondeterministic algorithm can be simulated by a deterministic machine in exponential time, NP ⊆ EXPTIME. In addition, P ⊆ EXPTIME and PSPACE ⊆ EXPTIME, while EXPTIME ⊆ EXPSPACE. The exact separations between these classes are established in many cases (for example, the time hierarchy theorem implies P ≠ EXPTIME).

EXPTIME-complete problems are the hardest problems in EXPTIME in the sense that every problem in EXPTIME can be reduced to them in polynomial time. Classic examples include the problem of determining the winner in generalized chess on an n-by-n board (under perfect play) and similar generalized two-player games like checkers. These results illustrate the rapid growth of required resources as problem description length grows and provide a canonical benchmark for exponential-time complexity.

Related notions include non-deterministic exponential time (NEXPTIME) and alternating-time classes. EXPTIME serves as a foundational benchmark in the study of algorithmic feasibility and the limits of deterministic computation.