Computational Complexity Theory
Computational complexity theory classifies problems by the amount of time, memory, and other resources any algorithm needs to solve them, drawing sharp lines between what is efficiently solvable and what appears to be intractable.
Definition
Computational complexity theory studies the intrinsic difficulty of computational problems measured by the resources, chiefly running time and memory, required to solve them on a model such as the Turing machine, and groups problems into complexity classes accordingly.
Scope
This area covers time and space complexity classes such as P, NP, PSPACE, and the polynomial hierarchy, the theory of NP-completeness and polynomial-time reductions, the central P versus NP question, and resource-bounded models incorporating randomness, interaction, and proofs, together with the hierarchy and hardness results that relate these classes.
Sub-topics
Core questions
- How much time and memory does solving a given problem inherently require?
- Which problems can be solved efficiently and which seem to resist all efficient algorithms?
- How are problems shown to be as hard as the hardest members of a complexity class?
- Do randomness, interaction, or nondeterminism add real computational power?
Key theories
- Time and space hierarchy theorems
- Given strictly more time or space, machines can solve strictly more problems, proving that complexity classes form genuine hierarchies and that some problems are inherently harder than others.
- NP-completeness
- The Cook–Levin theorem identifies problems in NP to which every other NP problem reduces, so a single efficient algorithm for any one of them would efficiently solve them all.
- Resource-bounded models
- Adding randomness, interaction, or alternation defines classes such as BPP, IP, and the polynomial hierarchy, whose relationships sharpen the picture of what extra resources can and cannot buy.
Clinical relevance
Complexity theory guides practice by certifying which problems admit efficient algorithms and which are NP-hard and therefore best attacked with heuristics or approximation; the presumed hardness of certain problems also underwrites modern cryptography, whose security rests on tasks believed to be computationally infeasible.
History
Hartmanis and Stearns founded the field in 1965 by defining complexity classes and proving hierarchy theorems. Cook and Levin introduced NP-completeness around 1971, Karp showed many natural problems complete in 1972, and the following decades added randomized, interactive, and probabilistically checkable proof models.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- What is the difference between computability and complexity?
- Computability asks whether a problem can be solved by any algorithm at all, ignoring cost. Complexity assumes the problem is solvable and asks how expensive that solution must be in time and memory, drawing finer distinctions among the problems that are solvable in principle.
- Why does NP-completeness matter in practice?
- When a problem is shown NP-complete, it is tied to thousands of others for which no efficient algorithm is known despite decades of effort. This signals that seeking a fast exact algorithm is likely futile and that approximation, heuristics, or special-case methods are the realistic path.