Complexity Theory

Computational complexity theory classifies computational problems according to the resources — time, space, randomness — required to solve them, and studies the relationships between these resource classes. Where computability theory asks what can be computed at all, complexity theory asks what can be computed efficiently.

The central objects of study are complexity classes: P (problems solvable in polynomial time on a deterministic Turing Machine), NP (problems whose solutions can be verified in polynomial time), PSPACE, EXP, and dozens of others. The central open problem — whether P = NP — asks whether every problem whose solution can be quickly verified can also be quickly solved. Most theoretical computer scientists believe the answer is no, but no proof exists.

Complexity theory has direct consequences for cryptography (most modern encryption assumes P ≠ NP), optimization, Artificial Intelligence, and the study of what physical systems can compute within resource bounds. It is one of the few areas of mathematics where the most important questions remain provably open.