Difficulty: Intermediate to Advanced | Prerequisites: Basic Turing machine definitions, Big-O notation, Boolean logic (3SAT)
Complexity theory classifies decision problems by how hard they are to solve (or verify). P problems are efficiently solvable, NP problems are efficiently verifiable, and NP-Hard problems are at least as hard as everything in NP. Reductions let you prove a new problem is NP-Hard by showing that a known hard problem can be transformed into it in polynomial time.
P (polynomial time)
The class of decision problems solvable by a deterministic Turing machine in polynomial time. In simple terms, these are problems a computer can solve quickly (in a reasonable number of steps relative to input size).
NP (nondeterministic polynomial time)
The class of decision problems for which a proposed solution (certificate) can be verified in polynomial time. Think of it as: hard to solve, but easy to check.
NP-Hard
A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time. These are at least as hard as the hardest problems in NP, but they need not be in NP themselves.
NP-Complete (NPC)
A problem that is both in NP and NP-Hard. These sit at the boundary: the hardest problems in NP. If you could solve any one of them in polynomial time, you could solve all of NP in polynomial time.
Polynomial-time mapping reduction (Karp reduction)
A function f computable in polynomial time such that x is in language A if and only if f(x) is in language B. Written A ≤p B. In simple terms, it is a way of converting one problem into another without blowing up the input size.
Certificate
A piece of evidence (a proposed solution) that lets a verifier confirm a "yes" instance of a problem. For example, a satisfying assignment is a certificate for SAT.
Verifier
A polynomial-time algorithm that takes an input and a certificate and accepts if the certificate proves the input is a "yes" instance. A language is in NP if and only if it has an efficient verifier.
3SAT
The satisfiability problem restricted to Boolean formulas in conjunctive normal form where every clause has exactly three literals. A canonical NP-Complete problem used as the starting point for many reductions.
When an exam question asks you to classify a language into P, NP, NP-Hard, or NP-Complete, use these mental checkpoints in order.
L ∈ P: efficiently decidable
Can you solve it in polynomial time? Is it easy to decide (try to for 3n²)?
Do you think a TM may loop indefinitely on any instance x ∉ L?
Can you construct an algorithm to efficiently decide L? That is, one that accepts all x ∈ L and rejects all x ∉ L?
L ∈ NP: efficiently verifiable, decidable in EXP time
Try to come up with a certificate c for L (look for "there exists" or other variables in the definition of L). Is |c| poly(|x|)?
Can you come up with an algorithm to efficiently verify L with such a c? That is, V s.t. x ∈ L ⇔ ∃ c, V(x,c) accepts.
L ∈ NPH: at least as hard as every language in NP
Is L undecidable? If so, it is NP-Hard (but not NP-Complete).
Do you need to check all combinations of some sort to decide L (i.e. brute force)?
Can you reduce to it from known NP-Hard/NP-Complete problems? (HamPath, 3SAT, Graph Coloring, Vertex Cover, etc.)
L ∈ NPC: as hard as any other language in NP (the hardest problems in NP); L ∈ NP and L ∈ NPH
Is it somewhat easy to verify a solution, but finding that solution itself seems really difficult?
Solitaire is a one-player game on a finite rectangular grid of cells. Each cell has zero or more stones (black or white). The goal is to remove zero or more stones so that each row has only one colour of stone (or no stone at all) and each column has at least one stone.
Showing Solitaire ∈ NP
A certificate for Solitaire is simply the set of stones to remove. A verifier checks whether the two conditions (one colour per row, at least one stone per column) are met after removal. This runs in polynomial time, so Solitaire is in NP.
Reduction from 3SAT to Solitaire
Given a 3SAT instance φ with n variables x₁, ..., xₙ and m clauses c₁, ..., cₘ, construct a grid f(φ) with n rows and m columns, with stones placed as follows:
If literal xᵢ appears in clause cⱼ, place a white stone at entry (i, j)
If literal ¬xᵢ appears in clause cⱼ, place a black stone at entry (i, j)
Rows correspond to variables, columns correspond to clauses, and there are exactly three stones per column. The reduction runs in polynomial time because it allocates a grid of polynomial size and places at most one stone per literal in the formula.
Forward direction: φ ∈ 3SAT ⟹ f(φ) ∈ Solitaire
If φ has a satisfying assignment, use it to build the puzzle solution:
If xᵢ = true, remove every black stone in row i of f(φ)
If xᵢ = false, remove every white stone in row i of f(φ)
Each row now has stones of only one colour (or no stone at all). Each column j retains at least one stone because clause cⱼ has at least one true literal under the assignment, so the corresponding stone was not removed.
Reverse direction: f(φ) ∈ Solitaire ⟹ φ ∈ 3SAT
If f(φ) has a solution, construct a satisfying assignment by setting the variables xᵢ as follows:
If row i contains only white stones, set xᵢ = true
If row i contains only black stones, set xᵢ = false
If row i contains no stones, set xᵢ arbitrarily
Since each column j has at least one stone, clause cⱼ is satisfied by the design of f(φ). If there is a white stone at (i, j), then literal xᵢ appears in cⱼ and we set xᵢ = true, so cⱼ is satisfied. A similar argument holds for black stones.
Set Packing is defined as:
SetPacking = { (A, S₁, ..., Sₙ, k) : each Sᵢ ⊆ A, and some k of them are pairwise disjoint }
Recall that sets are pairwise disjoint if the intersection of any two of them is the empty set.
Proving IndependentSet ≤p SetPacking
The reduction f takes an instance of IndependentSet (an undirected graph G = (V, E) and an integer k) and maps it to a SetPacking instance. For each vertex v ∈ V, let Sᵥ be the set of edges incident to v:
Sᵥ = { (u, v) : (u, v) ∈ E }
The reduction's output f(G, k) is the SetPacking instance A = E, all the Sᵥ for v ∈ V, and k. The reduction is efficient: it iterates over each vertex and lists its incident edges.
Correctness
(G, k) ∈ IndependentSet ⟺ f(G, k) ∈ SetPacking
There exists an independent set I of size k in G if and only if k of the sets Sᵥ are pairwise disjoint.
The key observation: by construction, Sₐ ∩ Sᵦ ⊆ E is the set of all edges incident to both a and v. So Sₐ ∩ Sᵦ is the nonempty set { (u, v) } if (u, v) ∈ E, and is the empty set otherwise.
(⟹) If I is an independent set of size k, the k subsets Sᵥ for v ∈ I are pairwise disjoint. For any distinct u, v ∈ I, because I is an independent set in G, we have (u, v) ∉ E, so Sᵤ ∩ Sᵥ = ∅.
(⟸) If k of the sets Sᵥ are pairwise disjoint, let I denote the k corresponding vertices in G. This is an independent set because for all distinct u, v ∈ I, Sᵤ ∩ Sᵥ = ∅, which means (u, v) ∉ E.
Since IndependentSet is NP-Hard, this polynomial-time mapping reduction shows that SetPacking is NP-Hard as well.
Let A be an array of n items each with a weight of A[i]. Given an integer size B and a capacity K, the array is "packable" if we can split it into up to K partitions such that the sum of each partition is less than or equal to B.
Packable = { (A, B, K) | an array A with n elements, each element a rational number, can be partitioned into K subarrays such that the sum of each subarray is less than or equal to an integer B }
Showing Packable ∈ NP
A certificate c is a set of K non-intersecting subarrays of A. Construct a verifier V on input ((A, B, K), c):
If c is not made up of K subarrays, reject
Concatenate all subarrays of c then sort. If this does not equal A after it is sorted, reject
For each subarray in c, if the sum is > B in any, reject
Accept
The verifier is correct because a valid partitioning of A produces a certificate c which, when put together and sorted, equals A sorted. All subarray sums will be ≤ B. If there is no valid partitioning, no such certificate c exists. The verifier runs in O(n²) time, which is polynomial.
Showing Packable ∈ NP-Hard via Partition
We reduce from Partition, which is known to be NP-Complete:
Partition = { {A} : A is a set of 2m numbers which can be partitioned into 2 non-intersecting subsets with equal sums }
Define the mapping f: Σ* → Σ* by f({A}) = (A', 1, 2), where A'[i] = 2·A[i] / (Σ|A|).
This is an efficient mapping because we can calculate the sum of A in linear time and then compute each element of A' in linear time.
Forward direction: w = A ∈ Partition ⟹ f(w) ∈ Packable
If A ∈ Partition then A can be partitioned into two subsets that each sum to 1. If (A', 1, 2) ∈ Packable then there must exist a partitioning of A' into two subarrays that each have a sum ≤ 1. Since the total sum of A' is 2, each of the 2 partitions must sum to exactly 1 to meet the requirement of having sums ≤ 1.
This means the sum of the two subarrays is equal, which means there must exist a partitioning of A into two subarrays of equal size in the original set A.
Reverse direction: f(w) ∈ Packable ⟹ w ∈ Partition
Thus Partition ∈ NP-Hard, and since Partition is NP-Complete, Packable is NP-Hard.
The general pattern for proving a language L is in NP follows a standard recipe.
Step 1: State the purpose. You are proving that L is in NP by constructing a polynomial-time verifier V(x, c) that accepts if and only if x ∈ L.
Step 2: Define the certificate. The certificate c should encode a proposed solution. For a graph problem, this might be a set of vertices. For a satisfiability problem, this might be a variable assignment.
Check that the certificate has polynomial size in |x|. If it does not, the verifier cannot read it in polynomial time.
Step 3: Build the verifier. Write V(x, c) as pseudocode that:
Checks the format and validity of c
Verifies that c satisfies the constraints of the problem
Accepts or rejects accordingly
Step 4: Prove correctness. Show both directions:
If x ∈ L, then there exists a certificate c such that V(x, c) accepts
If V(x, c) accepts, then x ∈ L
Step 5: Prove efficiency. Argue that V runs in polynomial time. Count the dominant operations and express the runtime as O(nᵏ) for some constant k.
A common pitfall: claiming a verifier is efficient without analysing its runtime. Always state the specific polynomial bound.
Students often think NP means "not polynomial." It does not. NP stands for nondeterministic polynomial time, and P ⊆ NP, so every efficiently solvable problem is also in NP.
Students sometimes confuse the direction of a reduction. To show problem B is NP-Hard, you reduce a known NP-Hard problem A to B (A ≤p B), not the other way around. The reduction goes from the known-hard problem to the new one.
Showing a problem is in NP does not mean it is NP-Complete. You must also show it is NP-Hard (via a reduction from a known NP-Hard problem).
A problem can be NP-Hard without being in NP. The Halting Problem, for example, is NP-Hard but undecidable, so it is not in NP.
When proving a reduction is correct, both directions matter. Showing φ ∈ 3SAT ⟹ f(φ) ∈ B is only half the proof; you also need f(φ) ∈ B ⟹ φ ∈ 3SAT.
⚠️ Reductions are tested heavily. Know the 3SAT reduction template: define f, prove polynomial time, prove both directions of correctness.
⚠️ Classifying languages (P vs NP vs NPC vs NPH) is a common MCQ topic. Use the intuition checklist above.
⚠️ Verifier construction questions require you to state the certificate, write the verifier, prove correctness in both directions, and prove the runtime is polynomial. Missing any one of these loses marks.
⚠️ If a question says "B is NP-Complete and B ≤p A," you can conclude A is NP-Hard. You cannot conclude A is NP-Complete unless you separately show A ∈ NP. You also cannot conclude A is in NP from the reduction alone.
⚠️ When asked "suppose B is NP-Complete and we show B ≤p A, which of the following can we always conclude?" the valid conclusions are: A is NP-Hard; A is at least as hard as every problem in NP. Invalid conclusions: A is in NP; A is NP-Complete; none of the other choices are always valid.
True or False: Every NP-Complete problem is also NP-Hard. (True)
True or False: If P = NP, then every problem in NP is also in P. (True)
Fill in the blank: To show a problem B is NP-Hard, we reduce a known ______ problem to B. (NP-Hard or NP-Complete)
True or False: The certificate for an NP problem must have exponential size. (False, it must be polynomial in the input size)
True or False: If B is NP-Complete and B ≤p A, then A is NP-Complete. (False, we can only conclude A is NP-Hard; A might not be in NP)
Q: What are the two conditions required to prove a problem is NP-Complete?
A: You must show (1) the problem is in NP (by constructing a polynomial-time verifier with a polynomial-size certificate), and (2) the problem is NP-Hard (by reducing a known NP-Hard problem to it in polynomial time).
Q: Given a 3SAT instance with n variables and m clauses, describe how to construct the Solitaire grid and state its dimensions.
A: Create an n × m grid (n rows for variables, m columns for clauses). Place a white stone at (i, j) if xᵢ appears in cⱼ. Place a black stone at (i, j) if ¬xᵢ appears in cⱼ.
Q: In the reduction from IndependentSet to SetPacking, what does each set Sᵥ contain?
A: Sᵥ contains all edges in E that are incident to vertex v. That is, Sᵥ = { (u, v) : (u, v) ∈ E }.
Q: Why does showing Partition ≤p Packable prove Packable is NP-Hard?
A: Because Partition is NP-Complete (and therefore NP-Hard), and a polynomial-time reduction from an NP-Hard problem to Packable means that Packable is at least as hard as Partition, making it NP-Hard.
Q: Suppose language B is NP-Complete and we demonstrate B ≤p A. Can we conclude A is NP-Complete?
A: No. We can only conclude A is NP-Hard. To show A is NP-Complete, we would also need to show A ∈ NP separately.
NP-completeness, NP-hardness, polynomial-time reduction, Karp reduction, many-one reduction, 3SAT, satisfiability, Boolean satisfiability, independent set, set packing, partition problem, Packable, Solitaire game, complexity classes, P vs NP, certificate, verifier, decision problem, EECS 376, foundations of computer science, University of Michigan, computational complexity, Cook-Levin theorem