EXPTIME

EXPTIME is where the genuinely time-expensive problems live: those solvable in an exponential number of steps, like 2^(n^k) for some constant k. Picture a problem whose solution requires exploring a tree of possibilities that doubles in size with each extra bit of input. For small inputs it is fine, but the running time explodes so fast that even modest inputs become hopeless on any real computer. EXPTIME is the formal home of that explosion, the class one big jump up from polynomial time.

Formally, EXPTIME is the union over all constants k of TIME(2^(n^k)): the languages decidable by a deterministic Turing machine in time bounded by 2 to a polynomial. Its place on the map is firm at one end: P is contained in NP is contained in PSPACE is contained in EXPTIME. The last inclusion holds because a polynomial-space machine has at most 2^(poly) distinct configurations, and if it never repeats one (else it loops forever and never decides) it must halt within that exponential number of steps. So bounded space forces bounded time, just an exponentially larger amount of it.

What makes EXPTIME special is that we can PROVE it is strictly bigger than P. By the time hierarchy theorem, P is strictly contained in EXPTIME, one of the very few unconditional separations we have. So there genuinely exist decidable problems, like deciding certain generalized board games (n-by-n chess, checkers) with optimal play, that provably require exponential time and can never be solved in polynomial time, no matter how clever the algorithm. Caveat to keep straight: P strictly inside EXPTIME does NOT resolve P versus NP or P versus PSPACE; those classes are squeezed between P and EXPTIME, and we cannot yet prove any of the intermediate inclusions strict. EXPTIME is simply far enough above P that the hierarchy theorem can finally bite.