Other meanings of Computational complexity theory
Computer science
Computational complexity theory is the study of the resources required to solve computational problems. It compares problems by the time, memory, randomness, communication, or other resources needed by algorithms, especially as input size grows.
Computational complexity theory classifies problems by the resources required by algorithms as inputs become large. A computational problem is represented through an abstract machine, such as a deterministic or nondeterministic Turing machine, and complexity is measured mainly as a function of input length.1 The principal resources are running time and working memory, although researchers also study randomness, communication, circuit size, parallelism, and quantum operations.
Polynomial-time computation is treated as a practical boundary because polynomial growth is generally more manageable than exponential growth, even though the boundary is not an exact engineering rule. Complexity classes group problems with similar resource bounds. The class P contains problems solvable in deterministic polynomial time, while NP contains decision problems whose proposed solutions can be verified in polynomial time.2
Polynomial-time reductions let researchers compare problems by transforming one instance into another efficiently. If every problem in a class can be reduced to a problem X, then X is hard for that class; if X also belongs to the class, it is complete for the class.
Stephen Cook’s 1971 theorem showed that the Boolean satisfiability problem is NP-complete, establishing the first such result.3 Richard Karp soon demonstrated NP-completeness for 21 diverse combinatorial problems, including the traveling-salesperson decision problem and graph coloring.4 The P versus NP problem asks whether every efficiently verifiable problem is efficiently solvable. Its resolution would affect optimization, automated reasoning, cryptography, and scheduling; the Clay Mathematics Institute lists it as one of the Millennium Prize Problems.
Complexity theory studies a hierarchy of classes rather than a single divide between easy and hard problems. Classes such as coNP, PSPACE, and EXPTIME capture different relationships between verification, memory, and time; known containments include P within NP and NP within PSPACE, but many possible equalities remain unresolved.2
Randomized classes such as BPP allow algorithms to make controlled-error probabilistic decisions, while counting classes examine how many computation paths accept. Circuit complexity replaces machine steps with logical gates and can prove lower bounds for restricted circuit families. In practice, hardness results often guide the search for approximation algorithms, fixed-parameter algorithms, heuristics, or special-case methods rather than proving that useful computation is impossible.
Several important branches of complexity theory examine settings that ordinary P-versus-NP discussions conceal. Parameterized complexity separates dependence on a primary input size from dependence on a smaller parameter, allowing some apparently difficult problems to be tractable when the parameter is modest. Communication complexity asks how many bits two or more parties must exchange when each sees only part of an input.
Other edge cases include promise problems, whose inputs are guaranteed to satisfy a stated condition, and relativization, which studies machines equipped with oracle subroutines; Baker, Gill, and Solovay showed that oracle choices can produce worlds with P equal to NP and others with P unequal to NP.5 Quantum complexity is a separate model in which quantum algorithms can outperform known classical methods for some tasks; Shor’s factoring algorithm is a landmark example.6
Complexity bounds depend on the chosen computational model, encoding, resource measure, and type of problem; statements about practical feasibility therefore require context.
Help improve the encyclopedia. Reports go straight to the site manager.