A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
EXPTIME is the class of languages decidable in time 2^(p(n)) for polynomial p; EXPTIME strictly contains PSPACE by hierarchy theorems. EXPSPACE similarly bounds space exponentially. These classes represent problems solvable by explicit enumeration or exhaustive search but intractable for realistic instance sizes. Problems complete for EXPTIME include two-player game winner determination and deciding provability in certain formal systems—scenarios where checking all possibilities becomes unavoidable.
You have studied the polynomial time and space classes — P, NP, PSPACE — and the relationships between them. EXPTIME and EXPSPACE extend this framework to exponential resource bounds, capturing problems that require fundamentally more computation than anything in the polynomial classes. EXPTIME is the class of all decision problems solvable by a deterministic Turing machine in time 2^p(n) for some polynomial p(n), and EXPSPACE is the analogous class for space.
The most important structural fact about EXPTIME is that it *provably* contains problems not in P. This is established by the time hierarchy theorem, which says that strictly more time allows you to solve strictly more problems. While we cannot prove P ≠ NP or NP ≠ PSPACE (these remain open), we *can* prove P ≠ EXPTIME. This means EXPTIME-complete problems are certifiably intractable — not just conjectured hard, but mathematically proven to require more than polynomial time. This is a stronger hardness guarantee than NP-completeness, which relies on the unproven assumption that P ≠ NP.
What kinds of problems land in EXPTIME? The signature examples involve two-player games with perfect information. Consider generalized chess played on an n×n board: determining whether the first player has a guaranteed winning strategy is EXPTIME-complete. The intuition is that a winning strategy must account for every possible response by the opponent at every move, creating a game tree that branches exponentially. Unlike NP problems, where a short certificate can verify a "yes" answer, game-winning strategies may themselves be exponentially large — there is no compact witness to check. This is why EXPTIME problems resist the verify-in-polynomial-time structure that defines NP.
EXPSPACE follows the same pattern one level up: problems solvable with exponential memory. The space hierarchy theorem ensures EXPSPACE strictly contains PSPACE, just as EXPTIME strictly contains P. A concrete EXPSPACE-complete problem is the equivalence of regular expressions with exponentiation (squaring). The full containment chain is P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE, with at least the first-to-last and third-to-last inclusions known to be strict. These exponential classes mark the boundary between problems that are theoretically decidable but practically hopeless and those that admit feasible algorithms — a boundary that matters whenever you encounter a problem and need to know whether clever algorithms can help or whether brute-force enumeration is inherently unavoidable.