Complexity Class
/kəmˈplɛk.sɪ.ti klæs/ · Noun · Development · Origin: 1965
Definitions
Complexity Class is a category in computational complexity theory that groups computational problems according to the resources (time, space) required to solve them on a given type of machine. The most fundamental classes are P (problems solvable in polynomial time by a deterministic machine), NP (problems whose solutions can be verified in polynomial time), PSPACE (problems solvable using polynomial space), and EXPTIME (problems requiring exponential time). The P vs NP question, whether every problem whose solution can be quickly verified can also be quickly solved, is one of the most important open problems in mathematics and computer science, with a million-dollar Clay Millennium Prize for its resolution. NP-complete problems (like the traveling salesman problem, Boolean satisfiability, and graph coloring) are the hardest problems in NP, and proving that any one of them is in P would prove P = NP. Understanding complexity classes helps developers recognize when a problem is fundamentally hard and when approximate or heuristic solutions are necessary rather than exact ones.
In plain English: A way of sorting problems by how hard they are for computers to solve. Problems in the same class take roughly similar amounts of effort.
Example: "The problem is in NP-complete, so unless P = NP, there's no polynomial-time algorithm — we should look for approximations."
Origin Story
The taxonomy that organizes problems by how hard they are to solve
**Complexity classes** emerged from the work of Juris Hartmanis and Richard Stearns, who published the foundational paper 'On the Computational Complexity of Algorithms' in 1965, establishing time complexity as a formal concept and launching computational complexity theory.
The most famous classes are **P** (solvable in polynomial time), **NP** (verifiable in polynomial time), **NP-complete** (the hardest problems in NP), and **NP-hard** (at least as hard as NP-complete). Stephen Cook proved the first NP-complete problem in 1971; Richard Karp followed with 21 more in 1972.
The complexity zoo now contains over 500 named classes. Whether P equals NP is the most important open question in computer science (and one of the Millennium Prize Problems worth $1 million). Most experts believe P does not equal NP, but nobody can prove it.
Coined by: Juris Hartmanis, Richard Stearns (complexity theory); Stephen Cook, Richard Karp (NP-completeness)
Context: 1965 (Hartmanis-Stearns), 1971 (Cook), 1972 (Karp)
Fun fact: Hartmanis and Stearns won the Turing Award in 1993 for their foundational work. The 'complexity zoo' (maintained by Scott Aaronson) catalogs classes like BQP (quantum computers), IP (interactive proofs), and the delightfully named 'Almost-PSPACE.'