Course contentsShow
← Computer Science
Lesson 1894 of 2,87243. Complexity TheoryFree lesson

The Class EXP (Exponential Time)

Defining exponential-time complexity and problems requiring exponential resources like generalized chess.

The Class EXP (Exponential Time)

What you'll learn: You'll understand what exponential-time complexity means and why some problems unavoidably require exponential resources to solve.

Beyond Polynomial Time

So far you've seen P (polynomial time) and NP (nondeterministic polynomial). But some problems are provably harder—they require more than any polynomial amount of time. Enter EXP, the class of problems solvable in exponential time.

What is EXP?

EXP contains all decision problems that can be solved by a deterministic Turing machine in time O(2^(n^k)) for some constant k, where n is the input size.

In simpler terms: if an algorithm's runtime is something like 2^n, 2^(n²), or 10^n, it's exponential. While polynomial algorithms scale reasonably well (n³ is manageable even for moderately large n), exponential algorithms explode catastrophically. Computing 2^100 steps is astronomically infeasible, even on the fastest computers.

Classic Example: Generalized Chess

Consider a chess game on an n×n board with n pieces. Determining whether there's a forced win in generalized chess requires exponential time. The number of possible game configurations grows exponentially with board size, and exhaustively exploring all paths demands exponential resources. No polynomial-time algorithm is known—or expected—to solve this.

Why EXP Matters

EXP represents problems that are decidable (they have solutions) but computationally intractable at scale. We know P ⊆ NP ⊆ EXP, and we also know P ≠ EXP (proven!), meaning truly hard problems exist. Whether P = NP remains unknown, but exponential problems remind us that computational feasibility has real limits.

Key Takeaway: EXP is the class of problems solvable in exponential time (like 2^n); these problems are decidable but grow too fast to be practical for large inputs, with generalized chess being a canonical example.