Computational Complexity

Computational complexity asks how the resources needed to solve a problem grow as the input grows. Time is the most familiar resource. Memory, randomness, communication, and circuit size can matter too.

This subject gives you a map of computational difficulty. It helps you separate three questions:

1. Can any algorithm solve the problem?
2. If so, how much of a resource does an algorithm use?
3. Can every algorithm be forced to use at least some amount of that resource?

The first question belongs to computability. Complexity theory focuses on the next two.

Problems, inputs, and resource models

A problem describes a required output for every valid input. An algorithm is a method for producing that output. Complexity attaches a cost to the algorithm as a function of input size.

You must state what input size means. A graph might be measured by its vertices and edges. An integer is measured by the number of bits needed to represent it, not by its numeric value.

You must also state a model of computation. The model defines which operations count and what each operation costs. Complexity results use formal models such as Turing machines so that hardware details do not dominate the analysis.

Growth matters more than a stopwatch

Asymptotic analysis studies behavior as input size grows. It suppresses fixed machine speeds and constant factors so you can compare growth rates.

• Big-O, written O(g(n)), gives an asymptotic upper bound.
• Big-Omega, written Ω(g(n)), gives an asymptotic lower bound.
• Big-Theta, written Θ(g(n)), gives a tight asymptotic bound.

For example, 3n² + 2n + 7 is O(n²). The quadratic term eventually dominates the lower-order terms. Big-O does not mean an exact running time, and it does not automatically mean worst case. You must name the case being analyzed.

Common growth rates include constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial growth. A better growth rate can matter more than a faster processor when inputs become large.

Cases and resource trade-offs

One input size can contain many different inputs. An algorithm may behave differently on each one.

• Worst-case complexity bounds the most expensive input of a given size.
• Best-case complexity bounds the least expensive input.
• Average-case complexity depends on a stated probability distribution over inputs.

Time is not the only cost. An algorithm may use more memory to save time. A randomized algorithm may trade certainty for a bounded error probability. The right analysis names the resource and the assumptions.

Complexity classes

A decision problem has a yes-or-no answer. Decision problems let complexity theory group problems by the resources needed to decide them.

P contains decision problems solvable by a deterministic algorithm in polynomial time. NP contains decision problems whose yes answers have certificates verifiable in polynomial time. Every problem in P is also in NP.

Do not read NP as “not polynomial.” The letters mean nondeterministic polynomial time. Whether P equals NP remains open.

An NP-hard problem is at least as hard as every problem in NP under the chosen polynomial-time reduction. It does not need to be a decision problem or belong to NP. An NP-complete problem is both in NP and NP-hard.

Reductions transfer knowledge

A reduction transforms instances of problem A into instances of problem B while preserving answers. If the transformation and the use of B are efficient, an efficient algorithm for B would give an efficient algorithm for A.

This direction is easy to reverse by mistake. To show that B is hard, reduce a problem already known to be hard to B. A reduction from B to an easy problem shows a way to solve B; it does not establish B's hardness.

Reductions support two kinds of work:

• Algorithm design: convert a new problem into one you already know how to solve.
• Hardness proofs: show that an unexpectedly fast algorithm would also solve a known hard problem unexpectedly fast.

What a hardness result does and does not say

An NP-completeness result concerns worst-case behavior for a family of inputs. It does not prove that every instance is difficult. It also does not tell you to stop.

You can still use exact algorithms on small inputs, exploit special structure, parameterize the difficult part, approximate an optimum, or use heuristics. These choices change the guarantee, the accepted inputs, or both. State that change clearly.

Polynomial time is a theoretical boundary, not a promise of practical speed. A polynomial with a huge degree can be unusable. An exponential algorithm can work well on the small instances you actually have. Measurements and asymptotic analysis answer different questions, so use both.

Where to go next

First, practice deriving time and space costs from loops, recursion, and data structures. Next, learn formal models, decision problems, and polynomial-time reductions. Then study NP-completeness proofs. After that, explore space complexity, randomized complexity, approximation, parameterized complexity, and lower-bound techniques.