Frequently Asked Questions
The most-asked questions about complexity theory.
What is complexity theory, in one breath?
It is the branch of theoretical computer science that sorts computational problems into tiers of difficulty based on how much time, memory, or other resources an algorithm needs. Instead of asking whether a problem is solvable at all, it asks how hard it is to solve.
Who are the central figures every fan should know?
Stephen Cook and Leonid Levin independently laid the groundwork for the P vs NP framework in 1971, and Richard Karp then showed a broad family of problems were all equivalent in hardness. Later voices like Scott Aaronson, Sanjeev Arora, and the PCP-theorem authors have kept the field evolving.
What does P vs NP actually ask?
It asks whether every problem whose proposed answer you can check quickly also has a way to find that answer quickly. If P equals NP, then tasks like optimal scheduling or protein folding would be as routine as verifying a checksum.
Which complexity classes should a newcomer learn first?
Start with P (solvable in polynomial time), NP (answers verifiable in polynomial time), PSPACE (solvable with polynomial memory), and EXPTIME (requiring exponential time). Those four give you the backbone; classes like BPP, PH, and QP add nuance later.
Where do I start if I've never touched the subject?
Michael Sipser's 'Introduction to the Theory of Computation' walks you from finite automata up to complexity in a very readable, example-driven style. For a more narrative and playful tone, Scott Aaronson's blog posts and his book 'Quantum Computing Since Democritus' are excellent companions.
What does 'polynomial time' concretely mean?
It means the running time is bounded by some fixed power of the input size—n², n⁵, whatever—as opposed to something like 2ⁿ that doubles with each extra bit. In the field's vocabulary it draws the informal line between 'tractable' and 'intractable.'
What is a reduction, and why is it everywhere in the literature?
A reduction is a transformation showing that if you had an efficient solver for problem B, you could also solve problem A by first converting A into an instance of B. It is the engine behind every NP-completeness proof: you reduce a known-hard problem to your new one to certify its difficulty.
What exactly makes a problem NP-complete?
It must sit inside NP (its answers are checkable in polynomial time) and every other NP problem must be reducible to it in polynomial time. Karp's landmark 1972 paper listed 21 such problems, and thousands more have been added since.
What are a few landmark moments in the field's history?
Cook's 1971 paper and Karp's 1972 follow-up essentially founded modern complexity theory, and the Clay Mathematics Institute named P vs NP one of its seven Millennium Prize Problems in 2000. The PCP theorem of the 1990s and ongoing work on circuit lower bounds have repeatedly reshaped what we believe is provable.
How does complexity theory touch cryptography and machine learning?
Public-key cryptography rests on the assumption that problems like integer factorization are computationally hard, which is squarely a complexity-theoretic claim. In ML, knowing the worst-case complexity of training objectives or inference pipelines helps set realistic expectations about what models can do efficiently at scale.