Computational Complexity studies the intrinsic resource requirements of computational problems and algorithms, particularly as problem size grows. Whereas Algorithm Analysis often evaluates a particular procedure, complexity theory asks broader questions about the resources required to solve problems and about the relationships among classes of problems. Important resources include time and space, and complexity can be studied under deterministic, nondeterministic, randomised, parallel, quantum, or other computational models.
Complexity classes group decision problems according to the resources required by algorithms that solve them. The subject provides a framework for distinguishing problems that appear efficiently solvable from those for which known exact methods require much larger resources. It also studies reductions, completeness, lower bounds, hierarchy results, and the boundaries of efficient computation.
Time complexity classes include P, the class of decision problems solvable in polynomial time by deterministic algorithms, and NP, the class of decision problems for which proposed solutions can be verified in polynomial time by a deterministic machine, equivalently those solvable in polynomial time by a nondeterministic machine under the standard formulation. NP does not mean “non-polynomial”, and membership in NP does not establish that a problem is difficult in practice.
NP-complete problems are problems in NP to which every problem in NP can be reduced using an appropriate polynomial-time reduction. If any NP-complete problem has a polynomial-time algorithm, then every problem in NP does as well, establishing P equals NP. Despite extensive research, whether P equals NP remains an open question. NP-hard problems are at least as hard as every problem in NP under the relevant reduction but need not themselves belong to NP or even be decision problems.
Reductions are central to Computational Complexity because they formalise relationships between problems. A reduction transforms instances of one problem into instances of another in a way that preserves the relevant answer, allowing an efficient solution to the target problem to imply an efficient solution to the original problem. Polynomial-time many-one reductions are widely used when establishing NP-completeness.
To prove that a problem is NP-complete, one normally establishes that it belongs to NP and then demonstrates that a known NP-complete problem reduces to it. This differs from merely observing that a problem resembles another difficult problem. Reductions also apply outside NP, including complexity classes involving space, randomness, approximation, counting, parameterised computation, and cryptographic assumptions. The direction of a reduction matters: if problem A reduces to problem B, an efficient algorithm for B can yield an efficient algorithm for A, but the reverse conclusion does not automatically follow.
The distinction between tractable and intractable computation is central but more nuanced than simply dividing algorithms into “fast” and “slow”. Polynomial-time algorithms are generally regarded as tractable in classical complexity theory because polynomial growth is substantially better than exponential growth at large scales, although a high-degree polynomial can still be impractical. Exponential algorithms may nevertheless be useful for small instances, highly structured inputs, or problems where no efficient exact algorithm is known.
Complexity also includes parameterised approaches that exploit small secondary parameters, approximation algorithms that provide bounded-quality solutions, fixed-parameter tractable algorithms whose complexity is separated into a function of a parameter and a polynomial factor, and heuristic methods without worst-case guarantees. Practical feasibility therefore depends on input size, parameter values, constants, available resources, and acceptable approximation or reliability requirements.
Space complexity examines memory requirements and produces classes such as P-space and exponential-space classes. A problem may have significantly different time and space characteristics, and time-space trade-offs can allow additional memory to reduce computation or vice versa. Savitch's theorem, for example, establishes a relationship between nondeterministic and deterministic space complexity that illustrates how complexity classes can behave differently from time classes.
Complexity theory also studies hierarchy theorems showing that, under standard models, additional resources can strictly increase computational power for particular resource measures. These results demonstrate that resource bounds are not merely engineering conventions but have mathematically meaningful consequences. Complexity classes can also be combined with restrictions on randomness, counting, interaction, approximation, communication, or parameter structure, creating a broad taxonomy of computational difficulty.
Computational Complexity is closely related to undecidability, but the two concepts must not be confused. A decidable problem has some algorithm that eventually produces the correct answer for every valid input, while an undecidable problem has no algorithm that can always do so under the relevant computational model. Complexity theory primarily studies problems that are computable and asks how much resource is required to compute them.
The halting problem is a classical example of an undecidable problem, whereas problems such as travelling-salesperson decision variants are decidable but can be computationally difficult under known exact approaches. This distinction creates different levels of limitation: some tasks are computable efficiently, some are computable but apparently resource-intensive, and some are not algorithmically computable at all under the formal model.
Complexity results have practical consequences in optimisation, scheduling, routing, verification, cryptography, automated reasoning, machine learning, database processing, and many other fields. When a problem is known to be NP-hard, developers may choose approximation, heuristics, restricted problem instances, parameterised algorithms, exhaustive search with pruning, integer programming, or domain-specific methods rather than expecting a universally efficient exact algorithm.
Complexity theory also underpins modern cryptography because certain cryptographic constructions rely on computational problems being infeasible to solve under specified assumptions, although cryptographic security requires much more than merely labelling a problem “hard”. Complexity analysis can identify scalability barriers before substantial implementation work is undertaken and can motivate reformulation of a task into a tractable variant.
Computational Complexity does not provide a simple practical ranking of all algorithms or problems. Complexity classes are defined relative to formal computational models and asymptotic resource measures, and real systems have hardware limitations, parallelism, memory hierarchies, specialised instructions, and application-specific constraints. An NP-complete problem can have rapidly solvable instances in a particular application, while a problem in P can have a polynomial algorithm whose degree or constants make it unsuitable at realistic scales.
Likewise, an exponential algorithm may be entirely adequate for small inputs. Complexity results therefore provide structural information rather than universal performance predictions. Their major significance is that they clarify which computational resources are fundamentally required under stated assumptions, which problems can be transformed into one another, and why practical algorithm design often relies on exploiting structure, approximation, restrictions, randomisation, or additional domain information.
