Proof complexity
The length and computational structure of mathematical proofs.
2 problemsComputational complexity
The resources needed to solve computational problems.
Explore Computational complexity
Collections
Browse collectionsMillennium Prize Problems
Five open problems from Clay’s famous prize program, linking mathematics with computation and mathematical physics.
5 problemsLimits of computation
Algorithms, computational limits and the guarantees behind decisions.
49 problemsProofs and certificates
Which statements have short proofs, and how do proof methods compare?
3 problemsA few problems to explore
30 totalP versus NP
A proposed guest list can be checked against the rules. Does easy checking always come with an efficient way to find a list that works?
Unique Games conjecture
A special kind of constraint puzzle is predicted to remain hard even when almost all its rules can be satisfied.
Derandomization
Random choices help many algorithms run quickly. Can every efficient algorithm with a bounded error probability be replaced by an efficient deterministic one?
Quantum PCP conjecture
Can estimating a quantum system’s lowest energy remain computationally hard even when only a fixed amount of accuracy is required?
L versus NL
Can every computation that uses only logarithmic memory with nondeterministic choices be carried out using the same memory bound deterministically?
3SUM hypothesis
Can finding three integers with a specified additive relation be done faster than essentially quadratic time?