Complexity Class
A grouping of problems by the computational resources — time or memory — needed to solve them.
Complexity Class
A complexity class is a bucket that holds all problems solvable within some budget of resources — a bound on time (number of steps) or space (amount of memory), measured as a function of input size with Big-O Notation. Sorting problems into these buckets is how theorists map the landscape of difficulty: not "can this be solved?" (that is Decidability) but "how expensive is it, fundamentally?"
The classes nest inside one another like Russian dolls, from the comfortably efficient out to the astronomically expensive.
The headline classes
Every problem in P is also in NP (if you can solve it fast, you can check a solution fast — just re-solve). Whether the reverse holds — whether easy-to-check always means easy-to-solve — is the P versus NP question, the most famous open problem in the field.
Beyond NP the buckets keep growing:
- PSPACE — solvable using a polynomial amount of memory, with no limit on time. Roomy enough to contain all of NP. Many two-player games (generalized chess, Go) live here.
- EXP (EXPTIME) — solvable in exponential time O(2^{n^k}). Provably larger than P: some problems require exponential time, full stop.
What we know for certain is a chain of inclusions:
The frustrating state of knowledge
Here is the scandal: we know \mathrm{P} \subsetneq \mathrm{EXP} — the two endpoints of that chain are genuinely different. So at least one of the \subseteq links must be a strict \subsetneq. Yet we cannot prove a single one of the intermediate inclusions is strict. It is entirely possible (though wildly unlikely) that \mathrm{P} = \mathrm{NP} = \mathrm{PSPACE}, with the gap hiding entirely between PSPACE and EXP.
Why classes are robust
A crucial fact makes this whole taxonomy meaningful: the classes barely care about the machine. By the Church–Turing principle, reasonable models simulate each other with only polynomial overhead, so P is the same class whether you use a Turing machine, a laptop, or a register machine. That stability is what lets P and NP name real, hardware-independent facts about problems — and what makes NP-Completeness such a powerful tool.