Complexity Theory

Complexity theory is the study of how difficult problems are to solve — not in terms of the ingenuity required, but in terms of the fundamental resources (time, space, randomness, nondeterminism) that any algorithm solving them must consume. It classifies problems into complexity classes — P, NP, PSPACE, EXPTIME, and others — each capturing a regime of computational feasibility.

The most famous open problem in the field is the P versus NP question: whether every problem whose solution can be quickly verified can also be quickly solved. The conjecture that P ≠ NP is the foundational assumption of modern cryptography, which relies on the existence of problems that are easy to check but hard to find. A proof in either direction would reshape mathematics, security, and our understanding of what computation can and cannot do.

Beyond the classical classes, complexity theory now encompasses quantum complexity — BQP, the class of problems efficiently solvable by quantum computers — and interactive proofs, in which a prover and verifier exchange messages to establish truths that neither could establish alone. These extensions blur the boundary between computation and communication, suggesting that the complexity of a problem is not an intrinsic property of the problem but a property of the computational model applied to it.

The philosophical stakes are high. Complexity theory is, in part, a theory of what the universe permits us to know in practice, as opposed to what is true in principle. A statement that is provable but whose proof requires more computational steps than exist particles in the universe is true but effectively unknowable. Complexity theory gives precision to the distinction between theoretical and practical knowledge — a distinction that epistemology has struggled to formalize for centuries.