What Is Computational Complexity?

Computational complexity is a branch of theoretical computer science concerned with classifying computational problems according to the resources required to solve them and understanding how those resource requirements scale with input size. The central resources of interest are time, measured by the number of elementary steps an algorithm performs, and space, measured by the amount of memory it consumes. By placing problems into complexity classes, researchers identify which problems are fundamentally tractable, which are intractable, and which remain open questions despite decades of investigation.

The field draws from mathematical logic, combinatorics, and algorithm theory. It grew substantially in the 1960s and 1970s following the formalization of polynomial-time computability by Cobham and Edmonds, and the introduction by Cook and Karp of NP-completeness as a concept that unified a large family of apparently hard optimization problems. The theory of computational complexity is foundational to the design of algorithms and to modern cryptography, where hardness assumptions about specific complexity classes underpin the security of widely deployed systems.

Complexity Classes

A complexity class is a set of problems that can be solved within a given resource bound by a specified model of computation. The class P contains all decision problems solvable in polynomial time on a deterministic Turing machine, while NP contains problems whose solutions can be verified in polynomial time. The question of whether P equals NP is the most famous open problem in computer science, with a Clay Millennium Prize attached to its resolution. Beyond P and NP, the complexity zoo maintained by the Complexity Garden project at the University of Waterloo catalogs hundreds of complexity classes, including PSPACE, EXP, BPP for probabilistic computation, and QMA for quantum verifiable problems, illustrating the richness of the classification enterprise.

Algorithmic Efficiency and Lower Bounds

A core goal of complexity theory is establishing lower bounds: proofs that no algorithm for a given problem can run faster than some threshold. Upper bounds come from constructing efficient algorithms; lower bounds require formal mathematical argument about the structure of any possible algorithm. The study of algorithmic efficiency in this sense is distinct from empirical benchmarking, as it makes claims about all possible implementations, not just known ones. Graph drawing and graph-theoretic problems, such as maximum clique or graph coloring, figure heavily in complexity theory because many NP-complete problems reduce to graph problems, and the ACM SIGACT Symposium on Theory of Computing has been a primary venue for lower-bound results since its founding in 1969.

Reductions and Completeness

The notion of reduction is the primary tool for relating the difficulty of different problems. A problem A reduces to problem B if any instance of A can be transformed into an instance of B in polynomial time, implying that an efficient algorithm for B would yield an efficient algorithm for A. NP-completeness is defined as membership in NP together with the property that every NP problem reduces to it; the satisfiability problem SAT was the first shown to be NP-complete by Cook in 1971. Reductions also define completeness in other classes. The Sipser textbook Introduction to the Theory of Computation, widely used in university courses and referenced in IEEE curricula, formalizes these concepts for the engineering and computer science communities.

Applications

Computational complexity has applications in a wide range of disciplines, including:

• Cryptography, where hardness of factoring and discrete logarithm problems underlies public-key security
• Algorithm design, guiding the search for approximation algorithms when exact solutions are intractable
• Artificial intelligence, classifying the difficulty of planning, constraint satisfaction, and inference problems
• Database systems, informing query optimization and the complexity of relational algebra operations
• Quantum computing, through the study of BQP and its relationship to classical complexity classes