Complexity theory classifies problems, not programs, by the resources any algorithm needs to solve them: time, memory, randomness, communication. It explains why some problems have fast solutions and others seem to resist every attempt, and it underlies the security of modern cryptography.
Key concepts
- Decision problems and classes: P is solvable in polynomial time, NP is checkable in polynomial time, PSPACE needs only polynomial memory.
- Reductions: if problem A can be turned into problem B cheaply, then B is at least as hard as A.
- NP-completeness: the hardest problems in NP; a fast algorithm for one would give one for all.
- Hierarchy theorems: with more time or space you can provably solve more problems.
- Beyond worst case: approximation, randomised algorithms, average-case hardness and parameterised complexity.
Vocabulary
- Polynomial time: running time bounded by a power of the input size, the usual meaning of "efficient".
- Certificate: a short proof that a yes answer is correct, which can be checked quickly.
- Oracle: an imaginary black box that answers one question instantly, used to compare classes.
- P versus NP: the open question of whether every quickly checkable problem is quickly solvable.
What to study, in order
- Big-O and the Turing machine as a model of cost.
- Write a brute-force solver and a verifier for a problem such as subset sum; compare their growth.
- Learn polynomial reductions and prove a small one by hand, such as from 3-SAT to clique.
- Read the Cook-Levin theorem and see why SAT is the first NP-complete problem.
- Survey space classes, randomised classes and approximation, and match real tasks to a class.