Computational complexity theory is a branch of theoretical computer science that analyzes the resources needed to solve computational problems. It asks how the time, memory, or other resources used by an algorithm grow as the size of its input increases, and it groups problems into classes according to the best possible resource bounds. The subject links mathematical models of computation with practical concerns about feasibility and efficiency.
Basic measures and notation
The most common measures are time complexity (how many computation steps an algorithm uses) and space complexity (how much working memory it requires). Asymptotic notation such as O(·), Ω(·), and Θ(·) describes growth rates for large inputs and lets researchers compare algorithms independently of machine-specific details. Standard models of computation used for formal definitions include Turing machines, random-access machines, and combinational circuits.
Core concepts and classes
Complexity theory organizes problems into classes that reflect resource bounds. Typical classes include:
- P: problems solvable in polynomial time; often taken as tractable or efficiently solvable.
- NP: problems whose solutions can be verified in polynomial time; includes many important decision problems.
- PSPACE: problems solvable with polynomial space, regardless of time.
- Probabilistic classes such as BPP, and nondeterministic space classes like NL and L.
Within these classes are special problem types such as NP-complete problems, which are the hardest problems in NP under efficient reductions. If any NP-complete problem can be solved in polynomial time, then every problem in NP can be.
Techniques, reductions and hardness
Central techniques include reductions — transforming one problem into another in a way that preserves solvability within resource bounds — and diagonalization, which separates classes by constructing problems that require more resources. Completeness and hardness results use reductions to identify representative problems (for example, satisfiability is a canonical NP-complete problem). These methods help show why some problems resist efficient algorithms and point to limits on what is computable in practice.
History and significance
The field grew from early work on computability and the formal definition of algorithms. Landmark results in the early 1970s established the importance of NP-completeness and connected disparate problems through reductions. Computational complexity has deep implications across computer science, informing cryptography, optimization, algorithm design, and understanding of practical trade-offs between time and memory.
Applications and open questions
Complexity theory guides algorithm selection in practice, clarifies when approximation or randomized methods are appropriate, and explains inherent computational barriers. One of the most famous open questions — whether P = NP — asks if every problem whose solution can be quickly checked can also be quickly solved. This and other unresolved relationships between complexity classes remain central research topics with practical as well as theoretical consequences.
For further reading on the theoretical foundations and algorithm analysis, consult introductory texts and surveys in theoretical computer science. See also resources that survey algorithms and computational models via computer science overviews and detailed expositions about algorithms and complexity.