Time Complexity
From efficient algorithms to NP-completeness
1 The next question: how efficiently can we compute?
Computability theory asks whether a problem can be solved by any algorithm at all. Complexity theory asks a more practical question:
If a problem is computable, how many resources are required to solve it?
The resource studied in this chapter is primarily time, measured as a function of the size of the input. This leads to some of the central questions in computer science:
- Which problems have efficient algorithms?
- Which problems appear to require enormous amounts of time?
- How can we compare problems even before we know their best algorithms?
- If a proposed solution is easy to check, must it also be easy to find?
The last question is the famous P versus NP problem. It remains open.
1.1 Tractable and intractable problems
Informally, a problem is called tractable when it can be solved with a feasible amount of computation and intractable when known algorithms require resources that grow too quickly. In classical complexity theory, polynomial-time computation is used as the mathematical dividing line:
- Polynomial growth: \(n\), \(n^2\), \(n^3\), and more generally \(n^k\) for a fixed constant \(k\).
- Exponential growth: \(2^n\), \(3^n\), \(n!\), and similar functions.
This is a theoretical convention, not a promise about actual running time. An \(n^{100}\) algorithm is polynomial but impractical, while an exponential algorithm may work well on small inputs. Nevertheless, polynomial time is robust across reasonable machine models and generally scales much better.
The Complexity Zoo catalogs the many complexity classes that arise when we vary the available resources and computational model.
2 Describing growth with asymptotic notation
Asymptotic analysis focuses on how resource use grows for large inputs. It ignores constant factors and lower-order terms so that algorithms can be compared independently of a particular processor or programming language.
2.1 Big-O notation
Let \(f,g:\mathbb{N}\to\mathbb{R}_{\ge 0}\). We say
\[ f \in O(g) \]
if there are constants \(c>0\) and \(n_0\) such that
\[ 0 \le f(n) \le c\,g(n) \qquad \text{for every } n\ge n_0. \]
Thus Big-O gives an asymptotic upper bound. For example,
\[ 12n^2+n \in O(n^3), \]
although the tighter statement is \(12n^2+n\in\Theta(n^2)\).
Related notation includes:
| Notation | Meaning |
|---|---|
| \(O(g)\) | asymptotic upper bound |
| \(\Omega(g)\) | asymptotic lower bound |
| \(\Theta(g)\) | matching upper and lower bounds |
| \(o(g)\) | strict asymptotic upper bound |
2.2 The input-size issue
Suppose an algorithm adds the integers from \(1\) through \(m\) using a loop. It executes \(O(m)\) iterations. But complexity is measured in terms of the length of the encoded input, not necessarily its numeric value.
If \(m\) is written in binary, its encoding has
\[ n=\lceil\log_2(m+1)\rceil \]
bits. Therefore \(m\) can be as large as approximately \(2^n\), and the loop takes \(O(2^n)\) time as a function of input length. This distinction is crucial: an algorithm that is linear in a number’s value can be exponential in the number of bits used to represent it.
2.3 Algorithms versus problems
An algorithm has a running-time bound. A problem’s time complexity refers to the best possible algorithm for that problem under the chosen model.
For example, a particular sorting algorithm may take \(O(n^2)\) time, but comparison sorting can be done in \(O(n\log n)\) time and also has an \(\Omega(n\log n)\) lower bound. Algorithms such as radix sort can do better only by exploiting additional assumptions about how keys are represented.
3 Measuring time on Turing machines
For a deterministic Turing machine \(M\), the running time \(t_M(n)\) is the maximum number of steps that \(M\) takes on any input of length \(n\). We normally require a decider to halt on every input.
For a function \(t:\mathbb{N}\to\mathbb{N}\), define
\[ \operatorname{TIME}(t(n)) = \{L \mid L \text{ is decided by a deterministic TM in } O(t(n)) \text{ time}\}. \]
3.1 Do machine details matter?
Reasonable variants of the Turing-machine model may change running time, but usually only polynomially:
- A multitape Turing machine running in time \(t(n)\) can be simulated by a standard single-tape machine in \(O(t(n)^2)\) time.
- A nondeterministic Turing machine running in time \(t(n)\) can be simulated deterministically by exploring its computation tree in \(2^{O(t(n))}\) time.
The first result helps explain why polynomial time is regarded as machine-independent. The second reveals a potentially exponential gap between deterministic and nondeterministic computation.
4 The class P
The class \(P\) contains the languages decidable in polynomial time by a deterministic Turing machine:
\[ P=\bigcup_{k\ge 1}\operatorname{TIME}(n^k). \]
Examples include many familiar problems involving arithmetic, graph traversal, shortest paths, minimum spanning trees, and primality testing. In 2002, the AKS algorithm established that primality testing is in \(P\).
Why privilege polynomial time?
- Polynomial-time algorithms are closed under composition.
- Their status is stable across standard computational models.
- They often correspond to algorithms that scale meaningfully in practice.
Still, \(P\) is a mathematical model of feasibility rather than a perfect description of it.
5 Nondeterminism and the class NP
A nondeterministic machine can be imagined as branching among possible choices. It accepts if at least one computation branch accepts. Its running time is the length of the longest branch.
The class \(NP\) is
\[ NP=\bigcup_{k\ge 1}\operatorname{NTIME}(n^k). \]
An equivalent and often more useful definition uses verification:
A language is in \(NP\) if every yes-instance has a polynomial-size certificate that a deterministic polynomial-time verifier can check.
Formally, \(L\in NP\) if there is a polynomial-time verifier \(V\) and a polynomial \(p\) such that
\[ w\in L \iff \text{there exists a certificate } c, \quad |c|\le p(|w|), \quad V(w,c)=1. \]
The certificate does not need to explain how it was found. It only supplies enough evidence for efficient checking.
5.1 Examples of certificates
- Clique: For a graph \(G\) and integer \(k\), the certificate is a set of \(k\) vertices. Check that every pair is joined by an edge.
- Hamiltonian path: The certificate is an ordering of all vertices. Check that each vertex appears once and consecutive vertices are adjacent.
- Subset sum: The certificate identifies a subset. Add its values and compare the result with the target.
- Satisfiability: The certificate is a truth assignment. Evaluate the formula under that assignment.
Every problem in \(P\) is also in \(NP\): the verifier can simply solve the problem and ignore the certificate. Hence
\[ P\subseteq NP. \]
Whether the reverse inclusion holds is unknown.
5.2 What about no-instances?
The definition of \(NP\) provides efficiently checkable evidence for yes-instances. The class \(coNP\) contains complements of languages in \(NP\) and captures problems whose no-instances have this kind of evidence. It is not known whether
\[ NP=coNP. \]
6 Two puzzle examples
6.1 The Smiley Puzzle
The Smiley Puzzle asks whether a board of colored smiley pieces can be arranged to satisfy the puzzle’s rules. A completed arrangement is a certificate: a verifier checks the placement and all local constraints in polynomial time.
This shows that the decision version of the puzzle is in \(NP\). It does not, by itself, show that the puzzle is NP-complete; that conclusion additionally requires an NP-hardness reduction.
6.2 The pegboard puzzle
In the pegboard puzzle, a legal move jumps one peg over another into an empty hole and removes the jumped peg. The decision problem asks whether a given position can be reduced to a single peg.
A proposed sequence of moves is a certificate. The verifier checks that every move is legal and that the final position contains one peg. Because each move removes a peg, any successful sequence has polynomial length.
6.2.1 Decision versus search
The decision question asks only whether a solution exists; the search problem asks for the moves themselves. If we had a polynomial-time decision algorithm, we could recover a solution by trying the possible first moves and asking which resulting position remains solvable. Repeating this process uses only polynomially many decision calls because the branching factor and solution length are polynomially bounded.
7 Bounds must be interpreted carefully
Suppose the only algorithm we know for a puzzle tries exponentially many possibilities. This establishes an exponential upper bound:
\[ T(n)\in O(2^n). \]
It does not establish that every algorithm requires exponential time. To rule out polynomial algorithms, we would need an appropriate lower bound. This distinction is especially important for NP-complete problems:
Finding a polynomial-time algorithm for even one NP-complete problem would prove \(P=NP\).
No such algorithm is known, but neither has anyone proved that none can exist.
8 Boolean satisfiability
A Boolean formula is satisfiable if some assignment to its variables makes the formula true. The language
\[ SAT=\{\langle\varphi\rangle\mid \varphi \text{ is a satisfiable Boolean formula}\} \]
is in \(NP\): a truth assignment is a certificate, and evaluating a formula is efficient.
In 3SAT, the formula is in conjunctive normal form and every clause contains three literals. For example,
\[ (x_1\lor \neg x_2\lor x_4) \land (\neg x_1\lor x_3\lor x_5). \]
9 Polynomial-time reductions
A polynomial-time mapping reduction from language \(A\) to language \(B\), written
\[ A\le_P B, \]
is a polynomial-time computable function \(f\) satisfying
\[ w\in A \iff f(w)\in B. \]
The direction matters. The reduction transforms instances of \(A\) into instances of \(B\), so an efficient algorithm for \(B\) would yield an efficient algorithm for \(A\). Thus \(B\) is at least as hard as \(A\) under this reduction.
10 NP-hardness and NP-completeness
A problem \(B\) is NP-hard if every problem in \(NP\) polynomial-time reduces to it. It is NP-complete if
- \(B\in NP\), and
- \(B\) is NP-hard.
The Cook–Levin theorem states:
SAT is NP-complete.
The proof encodes the accepting computation history of any polynomial-time nondeterministic Turing machine as a Boolean formula. Once one NP-complete problem is known, new NP-completeness results can be established through chains of reductions.
To prove that a new problem \(B\) is NP-complete, the standard recipe is:
- Show that \(B\in NP\) by describing a polynomial-time verifier.
- Choose a known NP-complete problem \(A\).
- Construct a polynomial-time reduction \(A\le_P B\).
- Prove both directions: yes-instances map to yes-instances and no-instances map to no-instances.
Reducing \(B\) to a known hard problem would only show that \(B\) is no harder than that problem; it would not establish that \(B\) is NP-hard.
11 Example reduction: 3SAT to Clique
The Clique problem asks whether an undirected graph \(G\) contains a set of \(k\) vertices that are all pairwise adjacent.
Given a 3CNF formula \(\varphi\) with \(k\) clauses, construct a graph as follows:
- Create one vertex for every literal occurrence in every clause.
- Connect two vertices when they come from different clauses and their literals are not contradictory.
- Ask whether the graph contains a clique of size \(k\).
11.1 Why the reduction works
Suppose \(\varphi\) is satisfiable. In each clause, choose one literal made true by the satisfying assignment. No two chosen literals contradict each other, so their vertices are connected. The \(k\) selected vertices form a clique.
Conversely, suppose the graph has a clique of size \(k\). Vertices within the same clause were never connected, so the clique contains exactly one vertex from each clause. Because contradictory literals were not connected, the selected literals can be made simultaneously true. Extending those choices to a truth assignment satisfies every clause.
Therefore,
\[ \varphi\in 3SAT \iff \langle G,k\rangle\in CLIQUE, \]
and the construction is polynomial in the size of \(\varphi\). Since 3SAT is NP-complete and Clique is in \(NP\), Clique is NP-complete.
12 The P versus NP question
The central unresolved question is
\[ P\stackrel{?}{=}NP. \]
- If \(P=NP\), every problem whose solutions can be checked efficiently can also be solved efficiently.
- If \(P\ne NP\), some problems have efficiently verifiable solutions but no polynomial-time solving algorithm.
The question is one of the Clay Mathematics Institute’s Millennium Prize Problems. A correct proof carries a one-million-dollar prize, but its significance extends much further: it would reshape our understanding of algorithms, optimization, automated reasoning, cryptography, and mathematical discovery.
13 Chapter summary
- Complexity theory measures the resources required to solve computable problems.
- Asymptotic notation describes growth as input length increases.
- \(P\) contains problems decidable deterministically in polynomial time.
- \(NP\) contains problems whose yes-instances have polynomial-size, polynomial-time-checkable certificates.
- \(P\subseteq NP\), but whether \(P=NP\) is unknown.
- Polynomial-time reductions compare problem difficulty.
- NP-complete problems are both in \(NP\) and at least as hard as every problem in \(NP\).
- SAT was the first problem proved NP-complete; many other problems inherit NP-completeness through reductions.
- An exponential algorithm is only an upper bound unless a matching lower bound is proved.
The broader lesson is that computation is not only about what machines can do. It is also about what they can do with enough efficiency to matter.