47.02.01 · theoretical-cs / complexity-fundamentals

Time Complexity, P, NP, and Polynomial-Time Reductions

shipped3 tiersLean: none

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.1-7.4; Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §1-2.2 and §2.3-2.5 (time hierarchy, Ladner's theorem, the Cook-Levin theorem and the structure of NP-complete problems)

Intuition Beginner

Some problems are easy to solve. Sorting a list of numbers, finding the shortest path between two cities on a map, checking whether a number is prime — all of these can be done by algorithms that finish quickly, even for large inputs. "Quickly" here means the running time grows at most as a polynomial function of the input size: quadratic, cubic, and so on.

Other problems seem hard to solve but easy to check. Given a Sudoku puzzle, finding the solution might take a lot of searching, but if someone hands you a filled-in grid, you can verify it is correct just by scanning the rows, columns, and boxes. This is the essence of the class NP: problems where a proposed solution can be verified in polynomial time.

The question "does P equal NP?" asks whether every problem whose solution can be quickly checked can also be quickly solved. It is one of the seven Clay Millennium Prize Problems, with a one-million-dollar reward for its resolution. Most researchers believe P does not equal NP, but a proof remains elusive.

A polynomial-time reduction is a way of saying "if I could solve problem B quickly, I could also solve problem A quickly." It works by transforming any instance of A into an instance of B using a polynomial-time algorithm. If B is easy, then A becomes easy via the reduction. This is the tool that lets us compare the difficulty of problems without solving them.

Visual Beginner

The landscape of complexity classes:

All decidable problems
┌─────────────────────────────────────────┐
│                                         │
│   NP                                    │
│   ┌───────────────────────────┐         │
│   │  NP-complete              │         │
│   │  ┌────────────┐           │         │
│   │  │ SAT, 3SAT, │           │         │
│   │  │ Clique,    │           │         │
│   │  │ TSP (dec)  │           │         │
│   │  └────────────┘           │         │
│   │                           │         │
│   │  Graph iso?               │         │
│   │  Factoring?               │         │
│   │                           │         │
│   └───────────────────────────┘         │
│                                         │
│   P                                     │
│   ┌────────────┐                        │
│   │ Sorting,   │                        │
│   │ Shortest   │                        │
│   │ path,      │                        │
│   │ Primality  │                        │
│   └────────────┘                        │
│                                         │
└─────────────────────────────────────────┘

Class	Intuition	Example
P	Solvable in polynomial time	Is the graph connected?
NP	Verifiable in polynomial time	Does this graph have a Hamiltonian cycle?
NP-complete	Hardest problems in NP	SAT, 3SAT, Clique

Worked example Beginner

Consider the Clique problem: given a graph $G$ and an integer $k$ , does $G$ contain a clique (a completely connected subgraph) of size $k$ ?

This problem is in NP. Here is why: if someone claims "yes, there is a clique of size $k$ " and gives you the set of $k$ vertices, you can check by verifying that every pair among those $k$ vertices is connected by an edge. There are $k (k - 1) /2$ pairs to check, which is polynomial in the input size. So a proposed solution can be verified quickly.

Is Clique in P? No polynomial-time algorithm is known for general graphs. The best known algorithms take time exponential in $k$ (and for large $k$ , exponential in the graph size). But nobody has proved that no polynomial-time algorithm exists.

A polynomial-time reduction from 3SAT to Clique would show: if you could solve Clique quickly, you could also solve 3SAT quickly. Since 3SAT is NP-complete (proved in 47.02.02), this would make Clique NP-complete too.

Check your understanding Beginner

Formal definition Intermediate+

A Turing machine (as defined in 42.04.01) $M$ decides a language $L$ if for every input $w$ , $M$ halts and accepts when $w \in L$ and halts and rejects when $w \in / L$ . The time complexity of $M$ is the function $T_{M} : N \to N$ where $T_{M} (n)$ is the maximum number of steps $M$ takes on any input of length $n$ .

Definition (TIME and P). For a function $T : N \to N$ :

TIME (T (n)) = {L : there exists a TM M deciding L with T_{M} (n) = O (T (n))} .

The class P (polynomial time) is:

P = k = 1 ⋃ \infty TIME (n^{k}) .

Definition (NP, verifier definition). A language $L$ is in NP if there exists a polynomial $p$ and a polynomial-time Turing machine $V$ (the verifier) such that for all $x$ :

x \in L ⟺ \exists c \in {0, 1}^{p (∣ x ∣)} with V (x, c) = 1.

The string $c$ is called a certificate (or witness). The verifier $V$ runs in time polynomial in $∣ x ∣$ .

Definition (NP, NDTM definition). A language $L$ is in NP if there exists a polynomial-time nondeterministic Turing machine $N$ that accepts $L$ : $x \in L$ iff there exists an accepting computation path of $N$ on $x$ of length at most $p (∣ x ∣)$ for some polynomial $p$ .

The two definitions are equivalent: the certificate in the verifier definition encodes the sequence of nondeterministic choices in the NDTM definition.

Definition (polynomial-time reduction). A language $A$ is polynomial-time reducible to a language $B$ , written $A \leq_{p} B$ , if there exists a polynomial-time computable function $f : Σ^{*} \to Σ^{*}$ such that for all $x$ :

x \in A ⟺ f (x) \in B .

The relation $\leq_{p}$ is reflexive and transitive. If $A \leq_{p} B$ and $B \in P$ , then $A \in P$ (compose the reduction with the algorithm for $B$ ).

Definition (NP-completeness). A language $L$ is NP-complete if $L \in NP$ and for every $L^{'} \in NP$ , $L^{'} \leq_{p} L$ .

Counterexamples to common slips

"NP means 'not polynomial.'" NP stands for "nondeterministic polynomial time." It is a class of problems solvable in polynomial time on a nondeterministic machine, not a class of problems that are not polynomial.
"A problem in NP cannot be solved in polynomial time." P is a subset of NP, so every P problem is in NP. NP contains P; the question is whether it contains anything more.
"A polynomial-time reduction from A to B means A and B have the same difficulty." It means A is at most as hard as B (up to polynomial overhead). B could be much harder. Transitivity allows chaining: $A \leq_{p} B \leq_{p} C$ means $A \leq_{p} C$ .

Key theorem with proof Intermediate+

Theorem (P is closed under complement; NP is not known to be). If $L \in P$ , then $\overline{L} \in P$ . The same is not known for NP (i.e., it is unknown whether $NP = coNP$ ).

Proof. Let $M$ be a polynomial-time TM deciding $L$ . Construct $M^{'}$ that on input $x$ runs $M$ on $x$ and flips the answer: if $M$ accepts, $M^{'}$ rejects; if $M$ rejects, $M^{'}$ accepts. Then $M^{'}$ decides $\overline{L}$ in the same time as $M$ . $□$

The asymmetry for NP is fundamental: a verifier for $L$ checks existence of a good certificate, but $\overline{L}$ requires checking that no certificate exists, which is a universal quantifier. The question $NP = ? coNP$ is open and is related to, but distinct from, the P vs NP question.

Bridge. The P vs NP question is the foundational reason complexity theory has a structural backbone: the polynomial-time reduction $\leq_{p}$ creates a partial order on computational problems, and NP-complete problems sit at the top of this order within NP. This builds toward the Cook-Levin theorem in 47.02.02, where SAT is shown to be NP-complete by encoding arbitrary NP computations as Boolean formulas, and it appears again in 47.02.03 where the reduction chain SAT $\leq_{p}$ 3SAT $\leq_{p}$ Clique $\leq_{p}$ ... classifies dozens of problems as NP-complete at once. The central insight is that polynomial-time reductions transport both algorithms (if B is in P, so is A) and hardness (if A is NP-hard and $A \leq_{p} B$ , then B is NP-hard), and putting these together gives the entire edifice of NP-completeness.

Exercises Intermediate+

Exercise 8 (hard, short answer).

State and prove Ladner's theorem: if $P \neq = NP$ , then there exists a language in $NP ∖ P$ that is not NP-complete.

Hint

Construct a language that is "padded" SAT, where the padding grows at a rate determined by a function that diagonalises against all polynomial-time machines and all polynomial-time reductions.

Answer

The proof constructs a language $L_{H}$ by padding SAT with a function $H$ : $L_{H} = {x 0 1^{H (∣ x ∣)} : x \in SAT}$ where $H (n)$ is the smallest $i \leq lo g n$ such that the $i$ -th polynomial-time machine $M_{i}$ correctly decides SAT on all inputs of length $\leq lo g n$ (or $H (n) = lo g n$ if no such $i$ exists). The function $H$ grows slowly enough that $L_{H} \in NP$ (the padding is efficiently checkable), but fast enough that $L_{H} \in / P$ (diagonalising against each $M_{i}$ ) and $L_{H}$ is not NP-complete (any reduction from SAT to $L_{H}$ would force $H$ to be polynomially bounded, contradicting the diagonalisation). The full proof is in Arora & Barak §2.3.

Lean formalization Intermediate+

Mathlib has Computability.TuringMachine with basic TM definitions but no time-bounded complexity classes. The definition of TIME(T(n)) as a set of languages, the classes P and NP, polynomial-time reductions, and the transitivity of $\leq_{p}$ are absent. A Codex.Complexity.P module defining P via polynomial-bounded TM computations and proving robustness under model changes would be the foundational step; this unit ships without it.

Advanced results Master

Two structural results illuminate the landscape defined by P, NP, and reductions.

Theorem 1 (time hierarchy). For any time-constructible functions $f, g$ with $f (n) lo g f (n) = o (g (n))$ , $TIME (f (n)) ⊊ TIME (g (n))$ ^{[Arora & Barak §1.6]}. The proof is a diagonalisation argument: a universal machine simulates every $f (n)$ -time machine on its own encoding and flips the answer, running in $g (n)$ time. This shows that giving a Turing machine more time strictly increases its power — there are problems solvable in $n^{3}$ time but not in $n^{2}$ time, problems solvable in $2^{n}$ time but not in polynomial time, and so on.

Theorem 2 (Cook-Levin theorem, statement). The language $SAT = {φ : φ is a satisfiable Boolean formula}$ is NP-complete ^{[Arora & Barak §2.3]}. The proof constructs, for any NP machine $N$ and input $x$ , a Boolean formula $φ_{N, x}$ whose satisfying assignments encode accepting computation paths of $N$ on $x$ . The full proof is developed in 47.02.02.

Theorem 3 (robustness of P). The class P is the same regardless of whether we use single-tape Turing machines, multi-tape Turing machines, or RAM machines. A single-tape TM can simulate a $k$ -tape TM with quadratic overhead: $TIME_{k} (T (n)) \subseteq TIME_{1} (T (n)^{2})$ . A RAM machine can be simulated by a multi-tape TM with polynomial overhead ^{[Arora & Barak §1.3]}. This robustness is why P is a natural class: it does not depend on the specific computational model.

Synthesis. The P vs NP question is the foundational reason complexity theory organises problems by difficulty: polynomial-time reductions create a partial order, NP-complete problems are the maximal elements within NP, and the time hierarchy theorem ensures that this landscape has genuine structure (more time yields more power). The central insight is that the reduction $\leq_{p}$ transports both upper bounds (membership in P) and lower bounds (NP-hardness), and putting these together with the Cook-Levin theorem of 47.02.02 and the classical NP-completeness reductions of 47.02.03 classifies hundreds of natural problems into a small number of equivalence classes. This builds toward the polynomial hierarchy of 47.02.04, where the alternation of existential and universal quantifiers creates an infinite hierarchy of complexity classes, and appears again in the randomised classes of 47.03.01 where probabilistic computation potentially extends P.

Full proof set Master

Proposition 1 (equivalence of NP definitions). The verifier definition and the NDTM definition of NP are equivalent.

Proof. (Verifier $\Rightarrow$ NDTM): Let $V$ be a polynomial-time verifier for $L$ with certificate bound $p$ . Construct an NDTM $N$ that on input $x$ nondeterministically guesses a certificate $c$ of length $p (∣ x ∣)$ and runs $V (x, c)$ . If $x \in L$ , some certificate causes $V$ to accept, so $N$ has an accepting path. If $x \in / L$ , no certificate is accepted. (NDTM $\Rightarrow$ Verifier): Let $N$ be a polynomial-time NDTM for $L$ . The certificate encodes the sequence of nondeterministic choices (at each branch point, which transition to take). The verifier $V$ simulates $N$ deterministically using the choices from the certificate and accepts iff the simulation accepts. $□$

Proposition 2 (closure under polynomial-time reductions). If $A \leq_{p} B$ and $B \in P$ , then $A \in P$ .

Proof. Let $f$ reduce $A$ to $B$ in time $p_{1} (n)$ , and $M_{B}$ decide $B$ in time $p_{2} (n)$ . On input $x$ , compute $f (x)$ in time $p_{1} (∣ x ∣)$ , then run $M_{B}$ on $f (x)$ in time $p_{2} (∣ f (x) ∣) \leq p_{2} (p_{1} (∣ x ∣))$ . Total time: $p_{1} (n) + p_{2} (p_{1} (n))$ , a polynomial. Accept iff $M_{B}$ accepts. $□$

Proposition 3 (linear speedup). If $L \in TIME (T (n))$ and $c > 0$ , then $L \in TIME (c \cdot T (n) + O (n))$ .

Proof. Let $M$ decide $L$ in time $T (n)$ . Construct $M^{'}$ with a larger tape alphabet that encodes $k$ symbols of $M$ 's tape in one cell of $M^{'}$ 's tape, for $k$ large enough that the overhead of processing $k$ symbols is less than $c \cdot k$ steps. The simulation of one step of $M$ takes $O (1)$ steps of $M^{'}$ (scan the local $k$ -block, compute the new $k$ -block, write it back). Choosing $k$ sufficiently large gives the speedup factor. The initial encoding of the input takes $O (n)$ steps. $□$

Connections Master

42.04.01 — The Turing machine model defined there provides the computational framework on which time complexity is measured; the time-bounded classes P and NP are defined in terms of the halting behaviour of TMs within a step budget.
50.03.01 — Big-O notation and algorithmic complexity analysis give the formalism for measuring and comparing running times; the definition of P uses $O (n^{k})$ as the bound.
47.02.02 — The Cook-Levin theorem proves that SAT is NP-complete, establishing the first NP-complete problem and the foundation for all subsequent NP-completeness results.
47.02.03 — Classic NP-complete problems are classified by reduction chains from SAT, using the $\leq_{p}$ relation defined here.
47.02.04 — The polynomial hierarchy extends P and NP by alternating quantifiers over polynomial-time predicates, creating $Σ_{k}^{p}$ and $Π_{k}^{p}$ classes.

Historical & philosophical context Master

The class P was first studied by Alan Cobham (1964) and Jack Edmonds (1965), who independently argued that polynomial time captures the intuitive notion of "efficient computation." Cobham's paper "The Intrinsic Computational Difficulty of Functions" defined P using Turing machines and proved its robustness under model changes. Edmonds, in his paper on maximum matching, argued that polynomial-time algorithms represent "good" algorithms.

The class NP was defined by Stephen Cook in his 1971 paper "The Complexity of Theorem-Proving Procedures," where he also proved the NP-completeness of SAT. Richard Karp independently proved NP-completeness for 21 additional problems in his 1972 paper "Reducibility Among Combinatorial Problems," establishing the pervasiveness of NP-completeness across combinatorics, logic, and optimisation ^{[Arora & Barak §2.1]}.

Leonid Levin, working independently in the Soviet Union, also proved a version of the Cook-Levin theorem around 1971, and the result is sometimes called the Cook-Levin theorem in recognition of both contributions. The P vs NP question was formalised in these papers and has remained the central open problem in computational complexity theory.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{arora-barak2009,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{cook1971complexity,
  author  = {Cook, Stephen A.},
  title   = {The Complexity of Theorem-Proving Procedures},
  journal = {Proceedings of the 3rd Annual ACM Symposium on Theory of Computing},
  pages   = {151--158},
  year    = {1971},
}
@article{karp1972reducibility,
  author  = {Karp, Richard M.},
  title   = {Reducibility Among Combinatorial Problems},
  journal = {Complexity of Computer Computations},
  pages   = {85--103},
  year    = {1972},
  publisher = {Plenum Press},
}
@article{cobham1964intrinsic,
  author  = {Cobham, Alan},
  title   = {The Intrinsic Computational Difficulty of Functions},
  journal = {Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science},
  pages   = {24--30},
  year    = {1964},
}

Prerequisites

42.04.01
50.03.01

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.1-7.3 (measuring running time, the class P of problems solvable in polynomial time, the class NP of problems with verifiable solutions)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.1-7.4 (formal definitions of P and NP, polynomial-time reductions, NP-completeness, Cook-Levin theorem preview); Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §1-2 (Turing machine time bounds, P, NP, reductions)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §7.1-7.4; Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §1-2.2 and §2.3-2.5 (time hierarchy, Ladner's theorem, the Cook-Levin theorem and the structure of NP-complete problems)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 7.1 defines the running time of a Turing machine $M$ on input $w$ as the number of steps before $M$ halts, and the time complexity of $M$ as $T (n) = max {t : M halts within t steps on some input of length n}$ ; section 7.2 defines the complexity class $P = ⋃_{k} TIME (n^{k})$ as the set of languages decidable in polynomial time, and $NP$ as the set of languages $L$ for which a polynomial-time verifier $V$ exists: $x \in L ⟺ \exists c \in {0, 1}^{p (∣ x ∣)} V (x, c) = 1$ ; section 7.4 defines polynomial-time reductions $A \leq_{p} B$ via a poly-time computable $f$ with $x \in A ⟺ f (x) \in B$ .
Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 1 defines the standard single-tape and multi-tape Turing machine models with time bounds $T (n)$ , proves the linear speedup theorem and the polynomial equivalence of multi-tape and single-tape machines; Chapter 2 defines $P$ , $NP$ (via both the verifier and NDTM definitions), polynomial-time reductions, NP-completeness, and proves the Cook-Levin theorem: $SAT$ is NP-complete; Ladner's theorem shows that if $P \neq = NP$ then there exist languages in $NP ∖ P$ that are not NP-complete.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m