Computational complexity is a branch of computer science and mathematics that studies the resources required to solve computational problems. Its principal resources are running time and memory, measured as functions of input size. Whereas analysis of an algorithm examines a particular procedure, complexity theory investigates problems themselves: what resources suffice to solve them, and what resources every possible solution must require. It therefore distinguishes inefficient implementations from inherent computational difficulty. (introcs.cs.princeton.edu)
Computational models and input size
Complexity statements depend on a specified model of computation. A Turing machine provides a standard mathematical model in which computation proceeds through discrete steps on symbol-bearing tapes. Other models include random-access machines and Boolean circuits. Many conventional sequential models can simulate one another with polynomial overhead, making polynomial-time classifications more robust than exact running-time bounds. (claymath.org)
Input size usually means the length of an encoding, often counted in bits, rather than the numerical magnitude of an input. An integer (W) written in binary requires approximately (\log_2 W) bits. Consequently, a procedure polynomial in (W) need not be polynomial in its encoded length. Such distinctions matter for the knapsack problem and other numerical problems studied through pseudo-polynomial time algorithms. (cs.yale.edu)
The distinction between difficulty and impossibility is also important. Complexity theory principally concerns resource-bounded computation, while computability theory asks which problems are algorithmically solvable at all. The halting problem, for example, has no algorithm that correctly decides every instance; this differs from a decidable problem requiring very large resources. (cs.cmu.edu)
Time, space, and asymptotic bounds
Time complexity counts computational steps, while space complexity measures memory consumption. For an algorithm and input length (n), worst-case time is the maximum running time over inputs of that length. Average-case analysis instead requires a specified input distribution. For a randomized algorithm, expected running time may refer to its internal random choices rather than a distribution of inputs. (aofa.cs.princeton.edu)
Big-O notation expresses asymptotic upper bounds, suppressing constant factors and lower-order terms. The related symbols (\Omega) and (\Theta) denote lower and tight bounds. These symbols do not themselves mean worst, best, or average case: each can describe whichever resource function has been defined. Common growth rates include logarithmic, linear, (n\log n), quadratic, and exponential. (algs4.cs.princeton.edu)
For example, binary search uses logarithmically many comparisons on a sorted array, while comparison-based sorting has a worst-case lower bound of order (n\log n). Such results depend on the permitted operations: a comparison-model lower bound does not automatically apply to algorithms using additional properties of their inputs. (algs4.cs.princeton.edu)
Complexity classes
A complexity class groups problems according to resource bounds and computational models. Classes are commonly defined using decision problems, whose outputs are “yes” or “no.” Search and optimization problems have related, but distinct, formulations. Standard classes include:
- P: decision problems solvable by deterministic algorithms in polynomial time.
- NP: decision problems whose yes-instances have polynomial-length certificates verifiable in deterministic polynomial time; equivalently, problems decidable in nondeterministic polynomial time.
- PSPACE: decision problems solvable using polynomial space.
- EXPTIME: decision problems solvable in deterministic time (2^{n^{O(1)}}). (claymath.org)
Their established relationship is [ \mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXPTIME}. ] The time hierarchy theorem implies that P is strictly smaller than EXPTIME, although it does not establish which adjacent inclusion in this chain is strict. More generally, hierarchy theorems show that suitably larger resource bounds permit additional problems to be solved, subject to technical conditions on those bounds. (cs.cmu.edu)
Polynomial time is a theoretical benchmark, not a guarantee of practical speed. A high-degree polynomial or enormous constant may be prohibitive, while an exponential algorithm may work adequately on small or restricted instances. (cs.princeton.edu)
Reductions, completeness, and P versus NP
A polynomial-time reduction transforms instances of one problem into instances of another while preserving their answers. If problem (A) reduces to problem (B), an efficient algorithm for (B) yields one for (A). Reductions thus transfer algorithms and establish relative difficulty. (cs.yale.edu)
Under polynomial-time many-one reductions, a problem is NP-hard if every problem in NP reduces to it. It is NP-complete if it is both NP-hard and a member of NP. The Cook–Levin theorem establishes that the Boolean satisfiability problem is NP-complete, providing a foundation for proving other completeness results. NP-hard problems need not themselves belong to NP. (claymath.org)
The P versus NP problem asks whether P equals NP and remains unresolved. A polynomial-time algorithm for any NP-complete problem would imply P = NP. Conversely, NP-completeness alone does not prove that exponential time is necessary: even P ≠ NP would exclude polynomial-time algorithms, not automatically every subexponential algorithm. (claymath.org)
Randomness and broader applications
Randomized computation introduces classes such as BPP: problems decidable in polynomial time with error probability at most one third on every input. Independent repetition can reduce this error. Quantum computation has an analogous bounded-error polynomial-time class, BQP, defined using quantum rather than classical computation. (cs.yale.edu)
Complexity also studies circuit size and depth, communication, parallel computation, and the difficulty of counting solutions. In cryptography, security requires appropriate hardness assumptions, often involving typical rather than merely worst-case instances. An NP-hardness result therefore does not, by itself, establish cryptographic security. (cs.princeton.edu)