Difficulty: Intermediate to Advanced | Prerequisites: Basic complexity theory, polynomial time, decision problems
Reductions are the main tool for proving that a problem is computationally hard: you show that solving your new problem would also solve a known hard one. NP-completeness identifies the "hardest" problems in NP, the ones every other NP problem can be reduced to in polynomial time. If any single NP-complete problem turns out to have an efficient solution, then every problem in NP does, which is why most researchers believe P ≠ NP.
P
The set of all decision problems that can be decided (solved correctly on every input) in polynomial time by a deterministic Turing machine. In simple terms: problems a computer can solve quickly.
NP
The set of all decision problems for which a "yes" answer can be verified in polynomial time, given a suitable certificate. Think of it as: problems where you can check a proposed solution quickly, even if finding one from scratch might be slow.
NP-hard
A problem L is NP-hard if every problem in NP can be reduced to L in polynomial time (X ≤p L for all X in NP). In simple terms: at least as hard as the hardest problems in NP. An NP-hard problem need not be in NP itself.
NP-complete
A problem that is both in NP and NP-hard. Think of it as: the hardest problems inside NP. If you solve one efficiently, you solve them all.
co-NP
The set of problems for which "no" instances can be verified in polynomial time. In simple terms: the mirror image of NP, where you can efficiently check that something does not have a solution.
Polytime Mapping Reduction (Karp Reduction), A ≤p B
A polynomial-time computable function f such that x ∈ A if and only if f(x) ∈ B. Transforms instances of A into instances of B while preserving the yes/no answer. Think of it as: a fast translator that turns any question about A into an equivalent question about B.
Turing Reduction, A ≤T B
An algorithm that solves A using a "black box" (oracle) for B, running in polynomial time aside from oracle calls. In simple terms: you can solve A if someone hands you a magic solver for B.
Verifier
A polynomial-time algorithm V(x, c) that checks whether certificate c proves that input x is a "yes" instance. Think of it as: the exam grader. It cannot find the answer, but it can tell whether a proposed answer is correct.
Certificate (Witness)
A piece of evidence that lets the verifier confirm a "yes" answer. For a problem in NP, a valid certificate always exists for yes-instances and no certificate will fool the verifier on no-instances. In simple terms: the proof you hand to the grader.
Cook-Levin Theorem
The foundational result proving that SAT is NP-complete: for every language L in NP, there exists a polynomial-time computable function f such that x ∈ L ⟺ f(x) ∈ SAT. Think of it as: the original proof that SAT is the "universal" hard problem.
A Turing reduction from A to B (A ≤T B) shows that if you can solve B, you can solve A. You treat B as an oracle (a subroutine you can call freely) and build a polynomial-time algorithm for A around it.
If A ≤T B and B is decidable, then A is decidable.
If A ≤T B and A is undecidable, then B is undecidable.
Used to prove undecidability results (e.g., showing L_ACC is undecidable by reducing L_HALT to it).
To complete a Turing reduction argument you need two things: the reduction itself (the algorithm that uses the oracle) and a correctness argument showing the reduction works.
A polytime mapping reduction (Karp reduction) from A to B means there exists a polynomial-time computable function f such that for every input x: x ∈ A if and only if f(x) ∈ B.
Three things to show when proving A ≤p B:
Pseudocode for f: describe the polynomial-time function that maps instances of A to instances of B.
Correctness: prove both directions. If x ∈ A then f(x) ∈ B, and if f(x) ∈ B then x ∈ A.
Efficiency: argue that f runs in polynomial time.
Key implications:
If B ∈ P and A ≤p B, then A ∈ P.
If A is NP-hard and A ≤p B, then B is NP-hard.
"Problem B is at least as hard as Problem A."
All languages in NP are polytime reducible to any NP-complete language.
A problem L is in NP if there exists a polytime algorithm V (the verifier) such that:
Verify-L input: an instance x of the problem and a certificate c.
Verify-L output:
If x is a "yes" instance, there exists a c such that V(x, c) accepts.
If x is a "no" instance, V(x, c) rejects for every c.
The class NP is equivalent to the set of all problems whose solutions can be verified in polynomial time.
Relationship between classes:
P ⊆ NP (anything you can solve quickly, you can verify quickly).
NP ⊆ co-NP is unknown.
If NP ≠ co-NP, then P ≠ NP.
If NP ≠ co-NP, no NP-hard language sits in co-NP.
SAT: given a Boolean formula ϕ, is there a true/false assignment to its variables that makes ϕ true?
3SAT: SAT restricted to formulas in 3-CNF (conjunctive normal form where each clause has exactly 3 literals).
Vertex Cover: given a graph G and budget k, does G have a set of at most k vertices such that every edge has at least one endpoint in the set?
Clique: given a graph G and budget k, does G have a set of at least k vertices where every pair is connected by an edge?
Independent Set: given a graph G and budget k, does G have a set of at least k vertices with no edges between any pair?
Set Cover: given a universe U of elements, n subsets S₁ ... Sₙ ⊆ U, and budget k, can you cover all of U with at most k of the subsets?
Hamiltonian Path: given an undirected graph G and vertices s, t, is there a path from s to t that visits every vertex exactly once?
Hamiltonian Cycle: given an undirected graph G, is there a cycle visiting every vertex exactly once?
Max Cut: given a graph G and integer k, can the vertices be partitioned into two sets so that at least k edges cross between them?
Others in this family: Knapsack, SubsetSum.
When you have an algorithm for the decision version of an NP-complete problem, you can use it to find the actual solution (the search version) through repeated calls.
Example with Vertex Cover: use the decision algorithm ("is there a vertex cover of size k?") to identify which vertices belong to the cover. For each vertex v, tentatively remove v and its incident edges. If the resulting graph still has a vertex cover of size k−1, keep v out. Otherwise, v must be in the cover. Repeat until the cover is found.
This works because NP-complete decision problems and their search counterparts are polynomially related.
A \leq_p B \text{ (Karp):}\quad x \in A \iff f(x) \in B,\; f \text{ computable in poly time}A \leq_T B \text{ (Turing):}\quad \text{poly-time algorithm for } A \text{ using oracle for } B\text{Verifier } V(x, c):\quad x \in L \implies \exists\, c,\; V(x,c) = \text{accept}\;; \quad x \notin L \implies \forall\, c,\; V(x,c) = \text{reject}Implication chain for NP-completeness proofs:
To show B is NP-hard, pick a known NP-hard language A and show A ≤p B.
To show B is NP-complete, show B is NP-hard AND B ∈ NP (by exhibiting a polytime verifier).
co-NP relationships:
If NP ≠ co-NP, then P ≠ NP.
If NP ≠ co-NP, no NP-hard language is in co-NP.
Approximation ratio (for related approximation problems):
Minimisation: OPT ≤ ALG ≤ α × OPT, where α > 1.
Maximisation: OPT ≥ ALG ≥ α × OPT, where α < 1.
Students often think "NP" stands for "non-polynomial." It stands for "nondeterministic polynomial time." Problems in NP can sometimes be solved in polynomial time (every problem in P is also in NP).
The direction of a reduction matters enormously. To prove B is NP-hard, you reduce a known hard problem A to B (A ≤p B), not the other way round. Reducing B to A would only show that B is no harder than A.
Students frequently confuse NP-hard and NP-complete. NP-hard problems need not be in NP at all. NP-complete means NP-hard plus membership in NP.
A common error is assuming that because a problem is NP-complete, no instances can be solved quickly. NP-completeness is a worst-case statement. Many specific instances of NP-complete problems are easy.
⚠️ Reduction direction is the single most common source of lost marks. Always reduce FROM the known NP-hard problem TO the problem you want to prove hard.
⚠️ When asked to prove a problem is NP-complete, you need two parts: (1) show it is in NP by describing a verifier and certificate, and (2) show it is NP-hard by giving a polytime reduction from a known NP-complete problem.
⚠️ The Cook-Levin theorem is the base case: it proves SAT is NP-complete without reducing from another NP-complete problem. Every other NP-completeness proof in the course chains from SAT.
⚠️ Decision-to-search conversions are a common exam topic. You should be able to explain how a decision oracle for an NP-complete problem can be used to find an actual solution.
⚠️ Know the definitions of the major NP-complete problems (SAT, 3SAT, Vertex Cover, Clique, Independent Set, Hamiltonian Path/Cycle, Set Cover, Max Cut) and be ready to use any of them as the starting point for a reduction.
True or False: Every problem in P is also in NP. Answer: True.
True or False: If a problem is NP-hard, it must be in NP. Answer: False. NP-hard problems can lie outside NP.
Fill in the blank: To prove problem B is NP-hard, you reduce a known ______ problem to B. Answer: NP-hard (or NP-complete).
True or False: A ≤p B means "A is at least as hard as B." Answer: False. It means B is at least as hard as A.
Fill in the blank: The ______ theorem proves SAT is NP-complete without reducing from another NP-complete problem. Answer: Cook-Levin.
Q: Describe the three components needed to prove a polytime mapping reduction from problem A to problem B.
A: (1) A polynomial-time computable function f that maps instances of A to instances of B. (2) A correctness proof that x ∈ A ⟺ f(x) ∈ B, covering both directions. (3) An efficiency argument that f runs in polynomial time.
Q: Explain why showing A ≤p B proves that B is at least as hard as A.
A: If B were in P, then composing the polytime reduction f with the polytime algorithm for B would give a polytime algorithm for A, placing A in P as well. So B cannot be easier than A.
Q: Prove that if NP ≠ co-NP, then P ≠ NP.
A: P is closed under complementation (if L ∈ P, then the complement of L is also in P). So P ⊆ NP and P ⊆ co-NP, which means P ⊆ NP ∩ co-NP. If P = NP, then NP = P ⊆ co-NP and co-NP = co-P = P ⊆ NP, so NP = co-NP. Contrapositive: NP ≠ co-NP implies P ≠ NP.
Q: Given that Vertex Cover is NP-complete, outline how you would prove that Independent Set is NP-complete.
A: First, show Independent Set is in NP by providing a verifier: the certificate is the proposed independent set S, and the verifier checks that |S| ≥ k and that no two vertices in S share an edge, all in polynomial time. Second, reduce Vertex Cover to Independent Set: a set S is a vertex cover of G if and only if V \ S is an independent set of G. So (G, k) ∈ Vertex Cover ⟺ (G, |V| − k) ∈ Independent Set. This is computable in polynomial time.
Q: How does the decision-to-search reduction work for Vertex Cover?
A: Use the decision oracle repeatedly. Start with the full graph and budget k. For each vertex v, tentatively delete v and its edges. Ask the oracle whether the remaining graph has a vertex cover of size k − 1. If yes, include v in the cover, reduce k by 1, and continue with the smaller graph. If no, v is not needed; move on. After processing all vertices, the vertices you included form a minimum vertex cover.
Approximation algorithms connect directly here: once you know a problem is NP-hard, exact solutions in polynomial time are (almost certainly) impossible, so you turn to algorithms that guarantee a solution within some ratio of optimal. The Minimum Vertex Cover 2-approximation is the classic example.
Cryptography in EECS 376 rests on the assumption that certain problems (factoring, discrete log) are hard. This hardness assumption is meaningful only because of the P vs NP framework: if P = NP, most cryptographic schemes would break.
The Cook-Levin reduction from any NP problem to SAT uses ideas from Turing machine simulation that connect back to the computability material earlier in the course.
NP-complete, NP-hard, P vs NP, polynomial reduction, Karp reduction, mapping reduction, Turing reduction, oracle, verifier, certificate, witness, SAT, 3SAT, CNF, vertex cover, clique, independent set, set cover, Hamiltonian path, Hamiltonian cycle, max cut, knapsack, subset sum, Cook-Levin theorem, decision to search, co-NP, approximation ratio, EECS 376, foundations of computer science, complexity theory, University of Michigan