complexity theory

Classification of computational problems by the resources (time, space, randomness) required to solve them. The science of what is feasible to compute.

core classes

• P: problems solvable in polynomial time by a deterministic Turing machine
• NP: problems whose solutions are verifiable in polynomial time
• NP-complete: the hardest problems in NP, every NP problem reduces to them (Cook-Levin theorem)
• NP-hard: at least as hard as NP-complete, possibly harder
• PSPACE: problems solvable with polynomial space
• BPP: problems solvable in polynomial time with bounded error probability
• BQP: problems solvable by a quantum computer in polynomial time

key concepts

• reductions: proving one problem is at least as hard as another by transformation
• P vs NP: the central open question — does efficient verification imply efficient solution?
• Big-O notation: asymptotic resource bounds, the language of algorithms analysis
• circuit complexity: measuring computation by Boolean circuit size and depth

applications

cryptography relies on the assumption that certain problems (factoring, discrete log) are hard. zero knowledge proofs exploit the gap between proving and revealing. consensus algorithms face impossibility results (FLP theorem) rooted in complexity.