complexityclasses

Complexity classes are formal groupings of decision problems according to the resources required to solve them on a Turing machine. They provide a framework to compare the intrinsic difficulty of problems beyond asymptotic runtime. Most work focuses on time or space; time-based classes track how the running time grows with input size, while space-based classes track memory usage.

Time classes include P, the set of problems solvable in polynomial time by a deterministic Turing machine; NP, the set of problems whose solutions can be verified in polynomial time, or solved in nondeterministic polynomial time; and EXP, problems solvable in exponential time. Equivalently, NP consists of problems for which a certificate can be checked quickly.

Space classes include L (logarithmic space) and NL (nondeterministic logarithmic space); PSPACE for polynomial space. We have inclusions such as L ⊆ P ⊆ NP ⊆ EXP and NL ⊆ P; PSPACE ⊆ EXP. Relationships among these classes, especially whether P = NP or NP = PSPACE, are central open questions.

Many NP problems are complete for NP, meaning they are among the hardest in NP under polynomial-time reductions; if any NP-complete problem is solved in P, then P = NP. Other completeness notions exist for different classes.

In addition, randomized classes such as RP and BPP capture problems solvable efficiently with randomness; results about these classes inform derandomization and average-case complexity. The field studies how different resource bounds shape problem difficulty and the structure of their hierarchies.

These classifications are idealized models; real-world algorithms sometimes defy simple categorization.