i. Complexity Theory and NP-Hardness

Complexity theory studies the intrinsic difficulty of computational problems. Computability asks can this be solved at all?; complexity asks how efficiently?: it bounds the time and space any algorithm needs as a function of the input size $n$ (upper bounds by algorithms, lower bounds by proofs), classifies problems into complexity classes, and compares them by reductions to find the hardest problems of a class (completeness). Core questions: can every problem whose solution is easy to verify (NP) also be solved easily (P)? Which problems are inherently exponential? How do randomness, quantum mechanics or parallelism change what is efficient? Can unconditional lower bounds be proved, or must we rely on conjectures?

For contests the practical skill is narrower: recognise NP-hardness, stop searching for a polynomial algorithm, and read the constraints for the intended escape (small $n$, small parameter, special structure, pseudo-polynomial values).

Model of computation	Notes
deterministic Turing machine (DTM)	one computation path; time = transitions, space = tape cells
nondeterministic TM (NTM)	accepts if some path accepts; defines NP
randomized TM	random bits; BPP, RP, ZPP
quantum TM / quantum circuits	qubits and unitary gates; BQP
Boolean circuits	acyclic gate networks: size (gates) and depth; non-uniform
decision trees, comparison model	query complexity; sorting lower bounds

Resource measures: time, space, alternations (quantifier switches: polynomial hierarchy), communication (bits exchanged), circuit size and depth.

Asymptotic notation

Notation	Definition	Meaning, example
$T=O(f)$	$\exists c,n_0\forall n\ge n_0:T(n)\le cf(n)$	upper bound: bubble sort is $O(n^2)$
$T=\Omega (f)$	$\exists c>0,n_0\forall n\ge n_0:T(n)\ge cf(n)$	lower bound: comparison sorting is $\Omega (n\log n)$
$T=\Theta (f)$	both	tight: merge sort is $\Theta (n\log n)$
$T=o(f)$	$\forall c>0\exists n_0:T(n)<cf(n)$	strictly slower: $2n=o(n^2)$
$T=\omega (f)$	$\forall c>0\exists n_0:T(n)>cf(n)$	strictly faster: $2n^2=\omega (n)$

$O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(n^3)\subset O(2^n)\subset O(n!)$. Polynomial: $O(n^k)$ for a constant $k$; exponential: $2^{n^{\epsilon }}$, broadly $2^{\mathrm{poly}(n)}$. Space: in place $O(1)$ (heapsort, insertion sort), $O(\log n)$ (binary search, some traversals), $O(n)$ (merge sort, BFS), polynomial (PSPACE), exponential (brute-force SAT storing all assignments). Practical numbers per complexity are in Complexity and Analysis.

Complexity classes

Class	Definition	Iconic problems
L / NL	(non)deterministic $O(\log n)$ space	undirected / directed reachability (NL-complete)
P	DTM, polynomial time: “tractable”	sorting, shortest paths, MST, 2-SAT, matching, flow, LP, primality (AKS)
NP	NTM polynomial time = certificates verifiable in polynomial time	SAT, Hamiltonian cycle, TSP (decision), clique, vertex cover
co-NP	complements of NP problems	tautology, “no Hamiltonian cycle”
NP-complete	in NP and NP-hard	3-SAT, clique, vertex cover, set cover, knapsack (decision)
NP-hard	every NP problem reduces to it; need not be in NP	optimization versions (TSP, max clique), the halting problem
PH	constant number of alternations: ${\Sigma }_1=$ NP, ${\Pi }_1=$ co-NP, ${\Sigma }_{i+1}={\mathrm{NP}}^{{\Sigma }_i}$	QBF with bounded alternations ($\exists x\forall y\phi$ is ${\Sigma }_2$-complete)
PSPACE	polynomial space (may take exponential time)	QBF, generalized geography, Hex, Reversi, Sokoban, Rush Hour
EXPTIME	$2^{\mathrm{poly}(n)}$ time	generalized chess, checkers, Go (Japanese ko) on $n\times n$ boards
NEXPTIME, EXPSPACE	nondeterministic exponential time, exponential space	succinct SAT / circuit SAT; regular expressions with squaring (EXPSPACE-complete)
#P	counting accepting paths	sat, the permanent (counting perfect matchings)
PP	error $<\frac{1}{2}$ (unbounded)	MAJ-SAT; contains NP
RP / co-RP / ZPP / BPP	one-sided / zero / two-sided error randomized polynomial time	polynomial identity testing (co-RP), randomized quicksort (ZPP), Miller–Rabin: Randomized Algorithms
BQP	quantum, bounded error	factoring and discrete log (Shor); Grover gives a quadratic speed-up for unstructured search
QMA, NQP	quantum analogues of NP (bounded / unbounded error)	local Hamiltonian (QMA-complete)

Known inclusions: $\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{PH}\subseteq \mathrm{PSPACE}\subseteq \mathrm{EXPTIME}\subseteq \mathrm{NEXPTIME}\subseteq \mathrm{EXPSPACE}$; $\mathrm{P}\subseteq \mathrm{ZPP}=\mathrm{RP}\cap \text{co-RP}$, $\mathrm{RP}\subseteq \mathrm{NP}$, $\mathrm{RP}\subseteq \mathrm{BPP}\subseteq \mathrm{BQP}\subseteq \mathrm{PP}\subseteq \mathrm{PSPACE}$, $\mathrm{NP}\subseteq \mathrm{PP}$, $\mathrm{BQP}\subseteq \mathrm{QMA}$, $\mathrm{BPP}\subseteq \mathrm{P}/\mathrm{poly}$. Known separations (hierarchy theorems, by diagonalization): $\mathrm{P}\ne \mathrm{EXPTIME}$, $\mathrm{NL}\ne \mathrm{PSPACE}$, $\mathrm{PSPACE}\ne \mathrm{EXPSPACE}$, $\mathrm{NP}\ne \mathrm{NEXPTIME}$. Open: $\mathrm{P}$ vs $\mathrm{NP}$ (believed different), $\mathrm{NP}$ vs co-NP, $\mathrm{P}$ vs $\mathrm{PSPACE}$, $\mathrm{EXPTIME}$ vs $\mathrm{NEXPTIME}$, $\mathrm{P}$ vs $\mathrm{BPP}$ (believed equal: derandomization results under plausible assumptions), $\mathrm{BQP}$ vs $\mathrm{P}$ (believed different because of Shor), whether BQP contains NP-complete problems (believed not). If $\mathrm{P}=\mathrm{NP}$ then PH collapses to P; if $\mathrm{NP}=\text{co-NP}$ it collapses to NP; PH is believed infinite. Quantum computers solve SAT in $O^{\ast }(2^{n/2})$ with Grover: still exponential.

Reductions and completeness

Reduction	Definition
Karp (many-one) $A{\le }_{p}B$	a polynomial-time $f$ with $x\in A⟺f(x)\in B$; defines NP-completeness
Cook (Turing) $A{\le }_{T}B$	polynomial time with an oracle for $B$, several calls allowed
log-space $A{\le }_{L}B$	the reduction uses $O(\log n)$ space; for classes inside P (NL, P-completeness)

Proving NP-completeness: (1) show the problem is in NP (a certificate checkable in polynomial time); (2) pick a known NP-complete problem $K$ close to it; (3) build a polynomial reduction from $K$ to the new problem; (4) prove both directions of “$K$-instance is yes $⟺$ constructed instance is yes”. Direction matters: reducing the new problem to a hard problem says nothing about its hardness (that is the classic error); reducing it to an easy problem gives an algorithm. Avoid constructions of exponential size.

                      SAT  (Cook-Levin: the first NP-complete problem)
                       |
                     3-SAT
        /         /    |     \             \
  3-COLORING  CLIQUE  SUBSET-SUM   HAMILTONIAN-CYCLE   3-DIM MATCHING
      |          |         |               |                 |
  planar 3-col  IND-SET  PARTITION        TSP          EXACT COVER, SET PACKING
                  |         |
             VERTEX-COVER  KNAPSACK, BIN PACKING, 3-PARTITION -> scheduling
                  |
              SET COVER, HITTING SET, DOMINATING SET -> facility location

Source	Natural targets
SAT / 3-SAT	logic, constraints, circuits: circuit SAT, NAE-SAT, Max-SAT, colouring, scheduling
clique / independent set	graph existence: vertex cover, dominating set
vertex cover	covering: set cover, hitting set, dominating set
Hamiltonian cycle	tours and paths: TSP, longest path, Steiner tree
set cover	set systems: hitting set, dominating set, facility location
subset sum / partition	numbers: knapsack, bin packing, scheduling (3-partition for strong hardness)
3-dimensional matching	packing with triples: set packing, exact cover, partition into triangles
Euclidean TSP, geometric set cover	geometry
3-partition, job shop	scheduling

// 3-SAT -> Independent Set (Karp): one triangle per clause, an edge between complementary literals.
// The formula (m clauses) is satisfiable iff the graph has an independent set of size m.
pair<int, vector<pair<int, int>>> threeSatToIndependentSet(const vector<array<int, 3>>& clauses) {   // literals +-(v+1)
    int m = sz(clauses); vector<pair<int, int>> E;
    for (int c = 0; c < m; c++) for (int i = 0; i < 3; i++) for (int j = i + 1; j < 3; j++) E.push_back({3 * c + i, 3 * c + j});
    for (int a = 0; a < 3 * m; a++) for (int b = a + 1; b < 3 * m; b++)
        if (clauses[a / 3][a % 3] == -clauses[b / 3][b % 3]) E.push_back({a, b});
    return {3 * m, E};
}

Proof: hardness transfers along reductions, and the 3-SAT reduction is correct

Transitivity. If $A{\le }_{p}B$ via $f$ and $B{\le }_{p}C$ via $g$, then $x\in A⟺g(f(x))\in C$, and $g\circ f$ runs in polynomial time because $|f(x)|$ is polynomial in $|x|$. So if every NP problem reduces to $A$ and $A{\le }_{p}B$, every NP problem reduces to $B$: $B$ is NP-hard. If $B\in \mathrm{P}$ and $A{\le }_{p}B$, then $A\in \mathrm{P}$; hence a polynomial algorithm for one NP-complete problem gives $\mathrm{P}=\mathrm{NP}$. Cook–Levin (SAT is NP-complete) encodes the accepting computation tableau of a polynomial-time verifier as a CNF formula; it is the base of every chain.

3-SAT $\to$ independent set. If an assignment satisfies every clause, pick one true literal per clause: one vertex per triangle, and no two picked literals are complementary (both would be true), so they form an independent set of size $m$. Conversely an independent set of size $m$ has exactly one vertex in each triangle (two in a triangle are adjacent), and never two complementary literals; set those literals true (other variables arbitrarily): every clause has a true literal. The graph has $3m$ vertices and $O(m^2)$ edges. Checked against brute force (all assignments vs all vertex subsets) on random formulas. Independent set, clique (in the complement graph) and vertex cover (the complement of an independent set) are then NP-complete too.

The problem catalogue

Domain	In P (polynomial)
sorting and searching	comparison sort $O(n\log n)$, counting / radix / bucket sort $O(n+k)$, binary search, selection $O(n)$, range search $O(\log n+k)$
graphs	BFS, DFS, topological sort, SCC, bridges, Dijkstra $O(E\log V)$, Bellman–Ford $O(VE)$, Floyd–Warshall $O(V^3)$, max flow (Dinic, push-relabel), MST, bipartite (Hopcroft–Karp) and general (blossom) matching, min-cost flow, Hungarian $O(n^3)$, Euler tours, 2-SAT, LCA, union-find, HLD
strings	KMP, Z, Rabin–Karp, suffix array, suffix automaton and tree, Aho–Corasick, tries, longest common substring
geometry	convex hull, closest pair, sweep lines, half-plane intersection, point in polygon
number theory and algebra	gcd, modular exponentiation, Miller–Rabin, CRT, sieve, Gaussian elimination, matrix multiplication ($\omega <2.372$), FFT / NTT, LP (interior point, ellipsoid), primality (AKS)

Domain	NP-complete (decision versions)
logic	SAT (Cook–Levin), 3-SAT, 1-in-3 SAT, exact 3-SAT, NAE-SAT, circuit SAT, Max-SAT, weighted Max-SAT, 0-1 integer programming
graphs: cliques and covers	clique, independent set, vertex cover, edge dominating set, clique cover, balanced complete bipartite subgraph
graphs: domination and colouring	dominating set (total, connected, efficient), $k$-colouring ($k\ge 3$), chromatic number, domatic number, perfect code, power domination
graphs: paths and cycles	Hamiltonian cycle / path, longest path, Steiner tree, feedback vertex / arc set, $k$ disjoint paths (directed, or $k$ part of the input)
graphs: layout and structure	cutwidth, bandwidth, minimum linear arrangement, bisection, max cut, maximum acyclic subgraph, subgraph isomorphism, minimum fill-in, minimum equivalent digraph, graph motif, rainbow connection
sets	set cover, hitting set, exact cover (X3C), set packing, set splitting, maximum coverage, minimum test set
numbers	subset sum, partition, 3-partition (strongly), knapsack, bin packing, quadratic programming, quadratic assignment, linear ordering, simultaneous Diophantine approximation
scheduling	job / open / flow shop, multiprocessor makespan, deadlines, precedence constraints, timetabling (course, exam, nurse), setup times, interval scheduling with conflicts
packing and cutting	bin packing (with conflicts), strip packing, 2D/3D packing, cutting stock, multiple knapsack, partition into triangles
routing and location	TSP and variants (capacitated VRP, repairman, rural postman, orienteering, prize-collecting, bottleneck), mixed Chinese postman, facility location, $p$-median, $k$-center, hub location
geometry	Euclidean / rectilinear TSP and Steiner tree, geometric set cover and hitting set, art gallery, maximum independent set of geometric objects
strings	closest string / substring, LCS and shortest common supersequence of many strings, multiple sequence alignment, bounded Post correspondence
puzzles ($n\times n$)	Sudoku, Kakuro, Nonogram, Minesweeper consistency, Slither Link, Nurikabe, Masyu, Light Up, Battleship, Numberlink, Instant Insanity, $n$-queens completion, peg solitaire, SameGame, Tetris, Lemmings
compilers and hardware	register allocation, frequency assignment, Boolean formula and circuit minimization (beyond NP: ${\Sigma }_2$-complete in general)

Karp’s 21 (1972): SAT, 0-1 integer programming, clique, set packing, vertex cover, set cover, feedback node set, feedback arc set, directed and undirected Hamiltonian cycle, 3-SAT, chromatic number, clique cover, exact cover, hitting set, Steiner tree, 3-dimensional matching, knapsack, job sequencing, partition, max cut.

NP-hard optimization (need not be in NP): TSP, max clique and independent set, min vertex cover, chromatic number, min dominating set and set cover, Steiner tree, feedback sets, max cut, layout problems; vehicle routing, traveling tournament, minimum latency; makespan and $\sum w_j{C}_j$ scheduling, berth allocation, gate assignment, crew scheduling; facility location, $p$-median, $p$-center; bin packing, strip packing, cutting stock; integer and mixed integer programming, sparse PCA, tensor rank, matrix completion, minimum rank, Boolean matrix factorization; optimal decision trees, Bayesian network structure learning, ${\ell }_0$ feature selection, rule-list minimization, MDL; protein folding, genome assembly, haplotyping, phylogeny (maximum parsimony), molecular docking, Ising spin glasses; VLSI layout, routing and floorplanning; maximum common subgraph, cluster editing, correlation clustering, group and directed Steiner tree, survivable network design, symbolic regression.

Beyond NP	Problems
#P-complete	the permanent, counting perfect matchings, counting SAT solutions: counting can be harder than deciding (finding a perfect matching is polynomial)
PSPACE-complete	QBF (canonical), generalized geography, Hex, Reversi, Sokoban, Rush Hour, constraint logic, LTL model checking, planning, quantified CSP
EXPTIME-complete	generalized chess (Fraenkel–Lichtenstein), checkers (Robson), Go with Japanese ko (Robson), alternating TMs with exponential time
beyond	regular expressions with squaring: EXPSPACE-complete; with complement: non-elementary; Presburger arithmetic: decidable but $2^{2^{\Omega (n)}}$ time (Fischer–Rabin)
undecidable	halting problem, busy beaver, Post correspondence, Entscheidungsproblem / first-order validity (Church, Turing), Rice’s theorem (every non-trivial semantic property, e.g. program equivalence), Hilbert’s tenth problem (Matiyasevich), word problem for semigroups and groups, matrix mortality (from $3\times 3$), Wang tiling

Easy–hard pairs worth memorising

Hard	Easy neighbour
3-SAT	2-SAT: linear, SCC
3-colouring	2-colouring (bipartiteness)
Hamiltonian path / cycle	Euler path / circuit
longest path in a general graph	longest path in a DAG
vertex cover, independent set in general graphs	bipartite graphs (Kőnig, matching)
max cut	min cut
integer programming	linear programming
TSP	MST, shortest paths
subset sum, knapsack	pseudo-polynomial DP when values are small (weakly NP-hard)
counting perfect matchings	deciding a perfect matching; counting spanning trees (matrix–tree)
graph isomorphism	quasi-polynomial (Babai 2015): not known to be in P or NP-complete
factoring	in NP $\cap$ co-NP, not believed NP-complete

	Weakly NP-hard	Strongly NP-hard
pseudo-polynomial algorithm	exists	none unless P = NP
FPTAS	possible	impossible unless P = NP
examples	subset sum, knapsack, partition	TSP, bin packing, 3-partition, clique

Knapsack’s $O(nW)$ DP is polynomial in the value $W$ but exponential in its length $\log W$: that is what “pseudo-polynomial” and “weakly NP-hard” mean, and why knapsack has an FPTAS (Approximation Algorithms) but TSP does not.

When you recognise NP-hardness

Stop looking for a polynomial exact algorithm and read the constraints:

Constraint	Approach
$n\le 20$	bitmask DP over subsets
$n\le 40$–$45$	meet in the middle
$n\le 100$, sparse or structured	branch and bound, good pruning
a small parameter $k$ (solution size, terminals, special vertices)	FPT algorithm, subset DP over the $k$ items
bounded values ($\sum w\le 10^6$)	pseudo-polynomial DP
the graph is a tree	tree DP: independent set, dominating set, vertex cover, colouring, Steiner tree are all linear on trees
bipartite	matching and flow
planar	separators, specialised algorithms
small treewidth, cactus	DP over a tree decomposition
scored / marathon task	heuristics: Heuristic Optimization

Best known exact algorithms	Time	Space
TSP, Hamiltonian cycle (Held–Karp)	$O(n^2{2}^n)$	$O(n{2}^n)$
maximum independent set / clique (branching)	$O(1.1996^n)$	polynomial
vertex cover (FPT branching)	$O(1.2738^k+kn)$	polynomial
graph colouring (inclusion–exclusion)	$O(2^{n}n)$	$O(2^n)$
Steiner tree (Dreyfus–Wagner)	$O(3^{k}n+2^k{n}^2)$ (plus shortest paths)	$O(2^{k}n)$
dominating set (branch and reduce)	$O(1.4969^n)$	polynomial
set cover over a universe of size $n$	$O(2^n\cdot m)$ DP	$O(2^n)$
0/1 knapsack	$O(nW)$ DP or $O(2^{n/2})$ meet in the middle
bin packing, job shop, quadratic assignment	branch and bound, ILP	exponential

Parameterized complexity

A problem is fixed-parameter tractable (FPT) in a parameter $k$ if it is solvable in $f(k)\cdot n^{O(1)}$: the explosion is confined to $k$. $O(n^k)$ is not FPT (the exponent depends on $k$): that is the class XP. Two independent sizes in the constraints ($n$ large, $k$ tiny) is the signature of an FPT problem.

Running time	Class	$n=10^5$, $k=10$
$2^{k}n$	FPT	$10^8$, fine
$1.28^k+kn$	FPT	$10^6$, fine
$k!n$	FPT	$3.6\cdot 10^{11}$, too slow (but FPT)
$n^k$	XP	astronomical

Problem	Parameter	Best known
vertex cover	solution size $k$	$O(1.2738^k+kn)$ (Chen, Kanj, Xia)
feedback vertex set	$k$	$O^{\ast }(3.619^k)$ deterministic, $O^{\ast }(2.7^k)$ randomized
$k$-path	$k$	$O^{\ast }(2^k)$ (algebraic); color coding $O^{\ast }((2e{)}^k)$: Randomized Search
Steiner tree	terminals $k$	$O(3^{k}n+2^k{n}^2)$: Steiner Tree
$d$-hitting set	$k$	$O(d^{k}n)$
closest string	number of strings	FPT
anything MSO-definable	treewidth $w$	$f(w)\cdot n$ (Courcelle); typical DPs $2^{O(w)}n$
independent set / clique	size	W[1]-hard
dominating set, set cover (number of sets)	size	W[2]-hard
colouring	number of colours	not FPT unless P = NP (NP-hard for 3)

$\mathrm{FPT}\subseteq \mathrm{W}[1]\subseteq \mathrm{W}[2]\subseteq \cdots \subseteq \mathrm{W}[\mathrm{P}]\subseteq \mathrm{XP}$; W[1]-hardness is the parameterized NP-hardness (no FPT algorithm unless FPT = W[1], Downey–Fellows). Note the asymmetry: vertex cover is FPT in $k$, but its complement, independent set, is W[1]-hard in its size.

Structure	Treewidth
tree, forest	1
cycle, cactus, series-parallel, outerplanar	2
$k\times n$ grid	$\min (k,n)$
planar	$O(\sqrt{n})$
complete graph $K_n$	$n-1$

Kernelization reduces an instance in polynomial time to an equivalent one whose size depends only on $k$, then solves the kernel by brute force. Buss’s kernel for vertex cover: a vertex of degree $>k$ must be in the cover (otherwise all its neighbours are); delete isolated vertices; if more than $k^2$ edges remain, answer no. The Nemhauser–Trotter LP gives a $2k$-vertex kernel. A decidable problem is FPT iff it has a kernel.

// Is there a vertex cover of size <= k? Buss kernel + branching on an edge: O(2^k k^2 + n + m).
bool vertexCoverAtMostK(int n, vector<pair<int, int>> E, int k) {
    while (true) {                                          // kernel: take vertices of degree > k
        if (k < 0) return false;
        vector<int> deg(n, 0); for (auto [u, v] : E) deg[u]++, deg[v]++;
        int big = -1; for (int v = 0; v < n; v++) if (deg[v] > k) { big = v; break; }
        if (big < 0) break;
        vector<pair<int, int>> F; for (auto e : E) if (e.first != big && e.second != big) F.push_back(e);
        E = F; k--;
    }
    if ((ll)sz(E) > (ll)k * k) return false;               // each cover vertex covers <= k edges
    auto branch = [&](auto&& self, const vector<pair<int, int>>& es, int kk) -> bool {
        if (es.empty()) return true;
        if (kk == 0) return false;
        auto [u, v] = es[0];
        for (int w : {u, v}) {                              // one endpoint of the edge is in the cover
            vector<pair<int, int>> F; for (auto e : es) if (e.first != w && e.second != w) F.push_back(e);
            if (self(self, F, kk - 1)) return true;
        }
        return false;
    };
    return branch(branch, E, k);
}

Proof: Buss's kernel, the branching, and FPT iff kernel

High degree. If $\mathrm{deg}(v)>k$ and $v$ is not in a cover $C$, all of $v$‘s neighbours are, so $|C|>k$; hence every cover of size $\le k$ contains $v$, and removing $v$ with its edges and decrementing $k$ preserves the answer. Edge bound. After that step every vertex has degree $\le k$, so $k$ vertices cover at most $k^2$ edges. Branching. Any cover contains an endpoint of every edge, so trying both endpoints of one edge explores every minimal cover; depth $\le k$, so at most $2^k$ leaves, each $O(k^2)$ work on the kernel. Checked against brute force over all vertex subsets of random graphs with up to 12 vertices.

FPT iff kernel. A kernel of size $g(k)$ gives FPT: kernelize, then brute force in a time depending on $k$ only. Conversely, given an $f(k)n^c$ algorithm: if $n\ge f(k)$, it runs in $n^{c+1}$, polynomial, so solve the instance and output a constant-size yes or no instance; otherwise $n<f(k)$ and the instance itself is a kernel of size $f(k)$.

Lower bounds

A lower bound proves that every algorithm in a stated model needs some amount of work. Reading an arbitrary input can require $\Omega (n)$ probes; outputting $k$ objects needs $\Omega (k)$ (printing all subsets is exponential even if each next subset is cheap); NP-hardness is conditional evidence, not a proven exponent, and an exponential known algorithm proves nothing about lower bounds.

Technique	Example
decision trees	comparison sorting needs $\lceil {\log }_{2}n!\rceil =\Omega (n\log n)$ comparisons; searching a sorted array needs $\lceil {\log }_2(n+1)\rceil$
adversary arguments	finding the maximum needs $n-1$ comparisons; minimum and maximum together need $\lceil 3n/2\rceil -2$; detecting a marked value needs $n$ probes
information / counting	any algorithm distinguishing $N$ outcomes needs ${\log }_{2}N$ bits of answers
reductions	sorting $\to$ convex hull gives $\Omega (n\log n)$ for hulls (algebraic decision trees)
communication complexity	set disjointness needs $\Omega (n)$ bits even with randomness; used for streaming and data-structure bounds
fine-grained (conditional)	SETH: no $O(n^{2-\epsilon })$ edit distance or LCS; 3SUM: no $O(n^{2-\epsilon })$ for many geometric problems; APSP conjecture

Proof: the decision-tree and adversary bounds

Decision trees. An algorithm making yes/no comparisons is a binary tree whose leaves are its possible outputs; to sort distinct values it must reach a different leaf for each of the $n!$ input orders, and a binary tree of height $h$ has at most $2^h$ leaves, so $h\ge {\log }_{2}n!\ge \frac{n}{2}{\log }_2\frac{n}{2}$. A three-way comparison makes the tree ternary (only the constant changes), equal elements reduce the number of distinguishable orders, and the bound says nothing about non-comparison algorithms (counting and radix sort on bounded keys). Insertion position in a sorted array has $n+1$ outcomes: $\lceil {\log }_2(n+1)\rceil$ comparisons.

Maximum. Every element except the maximum must lose at least one comparison (otherwise the adversary can make it the maximum, consistently with all answers), and a comparison has one loser: at least $n-1$ comparisons. Min and max. Compare elements in pairs ($\lfloor n/2\rfloor$ comparisons), then find the maximum among winners and the minimum among losers: $\lceil 3n/2\rceil -2$ in total. It is optimal: the algorithm must learn $2n-2$ facts ($n-1$ elements lose at least once, $n-1$ win at least once). A comparison of two never-compared elements yields 2 new facts; for every other comparison the adversary answers so that at most 1 new fact appears (a previous winner beats a fresh element, a previous loser loses to it, a winner beats a loser), consistently with some input. At most $\lfloor n/2\rfloor$ comparisons involve two fresh elements, so at least $\lfloor n/2\rfloor +(2n-2-2\lfloor n/2\rfloor )=\lceil 3n/2\rceil -2$ are needed. Marked value. The adversary answers “not marked” to every probe; until all $n$ positions are probed, both answers remain consistent with some input. The adversary’s answers must always stay consistent with at least one legal input: changing earlier answers is not allowed.

P vs NP and the rest of the landscape

P vs NP (a Millennium Prize problem): if $\mathrm{P}=\mathrm{NP}$, every NP-complete problem is efficiently solvable, which would transform optimization, AI and mathematics (automated proof search) and break cryptography based on factoring and discrete logarithms. If $\mathrm{P}\ne \mathrm{NP}$ (the general belief), easy verification does not imply easy solving, which justifies approximation algorithms and cryptographic hardness assumptions. Evidence: decades without a polynomial algorithm for any NP-complete problem, the collapse of PH that $\mathrm{P}=\mathrm{NP}$ would cause, and barrier results (relativization, natural proofs, algebrization) explaining why standard techniques cannot settle it. NP does not mean “non-polynomial”: every problem in P is in NP. Optimization problems are compared through their decision versions (“is there a tour of length $\le L$?”); certificates make membership in NP concrete (a Hamiltonian path is an ordering of the vertices: check adjacency and uniqueness; subset sum: the subset; 3-colourability: the colouring).

Circuit complexity (non-uniform; a circuit per input size; uniform families connect to TMs): NC (polynomial size, polylog depth: efficiently parallelizable; ${\mathrm{NC}}^i$ has depth $O({\log }^{i}n)$), AC⁰ (constant depth, unbounded fan-in AND/OR, NOT), AC⁰[m] (with MOD $m$ gates), ACC⁰ (any moduli), TC⁰ (threshold / MAJORITY gates), P/poly (polynomial size; contains P and BPP). Known: parity is not in AC⁰, so $\mathrm{A}{\mathrm{C}}^0⊊\mathrm{A}{\mathrm{C}}^0[2]$; $\mathrm{NEXP}⊈\mathrm{AC}{\mathrm{C}}^0$ (Williams, 2011). Open: whether $\mathrm{NP}\subseteq \mathrm{P}/\mathrm{poly}$ (showing $\mathrm{NP}⊈\mathrm{P}/\mathrm{poly}$ would prove $\mathrm{P}\ne \mathrm{NP}$), and even whether $\mathrm{PSPACE}\subseteq \mathrm{P}/\mathrm{poly}$; general circuit lower bounds are notoriously hard.

Communication complexity: bits that parties holding parts of the input must exchange (deterministic, randomized, quantum). Lower bounds via the rank of the communication matrix (approximate rank for randomized protocols); quantum communication can be exponentially smaller for some functions. Applications: circuit lower bounds, streaming, distributed databases, VLSI.

Descriptive complexity (logics on finite ordered structures): $\mathrm{NP}=\exists \mathrm{SO}$ (Fagin, 1974), $\mathrm{P}=\mathrm{FO}+\mathrm{LFP}$ (Immerman–Vardi), $\mathrm{PSPACE}=\mathrm{FO}+\mathrm{PFP}$, $\mathrm{NL}=\mathrm{FO}+\mathrm{TC}$, $\mathrm{PH}=$ second-order logic. Applications: database query languages, finite model theory.

Approximation and inapproximability (details and algorithms in Approximation Algorithms): ratio $\alpha$ means cost $\le \alpha \cdot OPT$ (minimization) or $\ge \alpha \cdot OPT$ (maximization); hardness via gap reductions and the PCP theorem.

Problem	Best ratio known	Hardness
metric TSP	$\frac{3}{2}-10^{-36}$ (Karlin, Klein, Oveis Gharan 2021; Christofides $\frac{3}{2}$)	no PTAS: NP-hard within $\frac{123}{122}$
general TSP	none	no constant ratio unless P = NP
vertex cover	2	NP-hard below $\sqrt{2}$ (Khot–Minzer–Safra; earlier 1.3606, Dinur–Safra); $2-\epsilon$ under the Unique Games Conjecture
set cover	$\ln n$ (greedy)	$(1-\epsilon )\ln n$ (Dinur–Steurer)
max cut	0.878 (Goemans–Williamson)	$\frac{16}{17}\approx 0.941$; 0.878 is tight under UGC
knapsack	FPTAS	none (weakly NP-hard)
bin packing	absolute $\frac{3}{2}$; asymptotically $OPT+O(\log OPT)$	absolute $\frac{3}{2}-\epsilon$ is NP-hard (from partition)
max clique	$O(n(\log \log n{)}^2/{\log }^{3}n)$ (Feige)	$n^{1-\epsilon }$ (Håstad, Zuckerman)

PTAS: $(1+\epsilon )$-approximation in $n^{f(1/\epsilon )}$; FPTAS: in $\mathrm{poly}(n,\frac{1}{\epsilon })$. The Unique Games Conjecture (Khot) would make many of these ratios tight; it is open.

Exercises

Describe certificates for subset sum and 3-colourability and contrast verifying with finding them. Given $n=10^5$ and only $k=15$ special vertices, design a state over the special vertices instead of all vertices. Reduce bipartite matching to flow and prove that integral unit flows correspond exactly to matchings. Derive the comparison lower bound for the insertion position in a sorted array. Explain why printing all subsets has an exponential output lower bound. Show how pairwise comparisons find minimum and maximum together faster than two scans.

Resources

• Garey and Johnson, Computers and Intractability (the NP-completeness catalogue); Papadimitriou, Computational Complexity; Sipser, Introduction to the Theory of Computation; Arora and Barak, Computational Complexity: A Modern Approach; Vazirani, Approximation Algorithms; Downey and Fellows, Parameterized Complexity.
• Complexity Zoo (complexityzoo.net); Wikipedia’s list of NP-complete problems and Karp’s 21; the Compendium of NP Optimization Problems (Crescenzi and Kann); the Open Problem Garden.
• Repositories: graphofnpcompletereductions (a graph of reductions), CodingThrust/problem-reductions, lawliet89/np-complete, GauravBh1010tt/Solving-NP-Hard-problems.

Related notes

• Approximation Algorithms
• Theoretical Algorithms Catalog
• Backtracking and Pruning