EXPTIME and Exponential Blowup
EXPTIME is the class of problems solvable in exponential time, and it provably contains problems that P cannot.
The class
EXPTIME contains every decision problem solvable by a deterministic algorithm in time O(2^p(n)) for some polynomial p. It is a huge class, encompassing exhaustive-search solutions to problems where the space of possibilities grows exponentially with input size.
A provable separation
Unlike the open P vs NP question, we know for certain that P is strictly smaller than EXPTIME. The time hierarchy theorem proves that more time buys strictly more computational power, so some EXPTIME problems provably have no polynomial-time algorithm.
EXPTIME-complete problems
- Deciding the winner in generalized chess, checkers, and Go on n-by-n boards
- Some problems in logic and automata equivalence
- Certain game and planning problems with exponential state spaces
Why blowup happens
Exponential time typically appears when an algorithm must consider all combinations of a set of choices: every subset (2^n), every ordering (n!), or every path in a branching tree. Each added element multiplies the possibilities, and no reformulation is known to avoid it for these problems.
The hierarchy above
EXPTIME sits inside an unbounded tower: NEXPTIME, 2-EXPTIME, and beyond, each provably larger than the last. Complexity theory shows an infinite ladder of ever-harder classes, all still decidable, before reaching the undecidable problems that no time bound can capture.
Practical meaning
An EXPTIME-complete problem is not merely believed hard; it is proven to need exponential time. There is no hope of a general polynomial algorithm, so effort goes entirely into small instances, special cases, or approximate and heuristic play, as in game-playing programs that search only a bounded depth.