Computational complexity theory

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.