Complexity Theory
Also known as: Computational Complexity
Study of resource requirements (time, space) for solving problems.
Computational Complexity Theory is the branch of computer science that studies the inherent resource requirements (time, space, randomness, communication, etc.) necessary to solve computational problems, classifying problems into complexity classes and proving relationships between them. The field's foundational concepts emerged from Alan Turing's 1936 work on computability and the Turing machine, with computational complexity as a distinct field developed through Hartmanis and Stearns's 1965 paper introducing time-complexity classes, Edmonds's 1965 articulation of polynomial-time as the boundary of practical solvability, Cobham's 1965 thesis identifying P with feasibly-solvable problems, Cook's 1971 introduction of NP-completeness, and Karp's 1972 demonstration that 21 important problems are NP-complete. The discipline's central open question — whether P = NP, that is, whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time — is the most famous open problem in computer science and one of the seven Clay Mathematics Institute Millennium Prize Problems. The framework's vocabulary (polynomial, exponential, NP-hard, NP-complete, intractable) has become standard for reasoning about algorithm scalability and is central to cryptography (which depends on certain problems being computationally intractable), optimization, and complexity-aware system design.
Core components
- Complexity classes (P, NP, NP-complete, NP-hard, PSPACE, EXPTIME, BPP, BQP, others)
- Polynomial-time as feasibility threshold
- NP-completeness and reductions between problems
- Time and space complexity hierarchies
- The P vs NP open problem
- Probabilistic and quantum complexity classes
- Approximation hardness and PCP theorem
- Lower bounds and unconditional vs conditional separations
Primary use case
Algorithm analysis and design; foundation for cryptography (depends on hardness assumptions including factoring, discrete log, lattice problems); intractability arguments justifying heuristic approaches to NP-hard problems; theoretical computer science research; pedagogical framework for understanding what computation can and cannot do efficiently; basis for thinking about quantum computing's computational implications.
Common criticisms
- Worst-case asymptotic framing — most relevant complexity-theory results — does not always reflect average-case or practical performance, leading to gaps between theoretical hardness and practical solvability (NP-hard problems often solvable in practice through heuristics, SMT solvers, etc.)
- P vs NP remains unresolved after 50+ years and unconditional lower-bound progress on most natural problems is glacial
- the assumption that 'polynomial-time = feasible' breaks down for high-degree polynomials
- quantum complexity and post-quantum classical algorithms have introduced new uncertainty about long-standing assumptions
- theoretical-vs-applied tension is real — many applied problems are 'NP-hard' in worst case but easily solved in practice
- some critics argue the asymptotic framing obscures more than it reveals about the actual cost structure of computation.