Computational complexity theory

Basic measures and notation

The two most common resources are time complexity (how many elementary steps an algorithm takes) and space complexity (how much memory it needs). Asymptotic notation such as Big O, Theta and Omega is used to describe growth rates for large inputs. Other measures include randomness (how many random bits are needed), communication (how much information must be exchanged between parties), and circuit size or depth for parallel computations.

Classes and common examples

• P: problems solvable in polynomial time by a deterministic machine (generally considered efficiently solvable).
• NP: problems whose solutions can be verified in polynomial time; includes many natural combinatorial problems.
• PSPACE, EXP and others: classes defined by larger resource bounds such as polynomial space or exponential time.

Complexity theory also studies completeness and hardness: a problem is complete for a class if it is among the toughest in that class. Reductions map instances of one problem to another to transfer hardness results and to organize problems into a hierarchy.

History and models

The field grew from early studies of computation and algorithms. Formal models such as the Turing machine, random-access machine (RAM), and Boolean circuits provide rigorous ways to define resource usage. Foundational results in the 1960s and 1970s established central notions like NP-completeness and introduced techniques for proving problems are unlikely to have efficient solutions. For background reading see introductory surveys or textbooks and lecture notes at educational sites.

Uses and importance

Complexity theory informs practical fields: it guides algorithm designers toward efficient methods, underpins cryptography by identifying hard problems that provide security, and helps set realistic expectations for optimization and scheduling. Knowing worst-case bounds gives guarantees about performance, while average-case and amortized analyses describe typical or long-run behavior.

Distinctions and open questions

Complexity differs from computability: a problem can be computable but still require impractical resources. Many central questions remain unresolved; the most famous is whether P equals NP, an open problem that asks if every efficiently verifiable solution can also be efficiently found. Advances also explore randomness (BPP), approximation algorithms, parameterized complexity, and new models including quantum complexity. For further reading and resources see curated bibliographies.