NP-Completeness

Chapter 1: Decision Problems

Before we can classify problems by difficulty, we need a common format. Optimization problems ask "what is the BEST solution?" — minimize this cost, maximize that profit. But "best" is slippery. Different problems have different objective functions, different solution formats, different notions of "better." Comparing them is like comparing apples and suspension bridges.

The fix is elegant: reframe everything as a yes/no question. Instead of "what is the shortest tour?", ask "is there a tour of length ≤ k?" Instead of "what is the maximum clique?", ask "does the graph have a clique of size ≥ k?" Same core difficulty, but now every problem has a simple binary output.

Formal Definition

A decision problem is a function that maps an input (called an instance) to either YES or NO. The set of all YES instances is called a language. An algorithm decides a language if it correctly returns YES for every instance in the language and NO for every instance not in the language.

The Class P

P is the class of decision problems that can be SOLVED in polynomial time. Formally: a language L is in P if there exists an algorithm A and a constant k such that for every input x of size n, A runs in O(n^k) time and correctly decides whether x ∈ L.

Here are some problems in P:

Notice the pattern: every one of these has a clever algorithm that avoids brute force. Dijkstra does not enumerate all paths. Hopcroft-Karp does not check all matchings. The algorithms exploit STRUCTURE in the problem to avoid exponential search.

Why Polynomial?

Why do we draw the line at polynomial time? Three reasons:

1. Closure under composition. If algorithm A runs in O(n²) and calls algorithm B which runs in O(m³), the composition runs in polynomial time. Polynomial is closed under addition, multiplication, and composition. Exponential is not.

2. Machine independence. If a problem is solvable in polynomial time on a single-tape Turing machine, it is solvable in polynomial time on a multi-tape Turing machine, a RAM machine, or any "reasonable" model of computation. The exponent may change, but polynomial stays polynomial.

3. Practical experience. Most polynomial-time algorithms have small exponents (1, 2, 3). Most exponential-time algorithms are truly impractical. The polynomial/exponential boundary, while imperfect, is the best simple dividing line between "feasible" and "infeasible."

Encoding Matters: Input Size

A subtle but critical point: the "n" in O(n^k) is the input size in bits, not the numerical value of the input. This distinction matters enormously for numeric problems.

Consider SUBSET-SUM. The input is a set of n numbers and a target T. A DP algorithm runs in O(nT) time. Is this polynomial? It depends on what "n" means.

If the input size is measured by the number of elements n and their values are small (say, at most polynomial in n), then O(nT) is polynomial. But if T is encoded in binary, the input size is about n · log(T) bits. Now O(nT) = O(n · 2^{log T}) — exponential in the input size! The DP is pseudo-polynomial: polynomial in the numeric VALUE but exponential in the number of BITS needed to represent it.

This distinction separates SUBSET-SUM (NP-complete but pseudo-polynomial) from problems like 3-SAT (NP-complete with no known pseudo-polynomial algorithm). It also explains why knapsack problems feel "easy" in practice when the weights and values are small integers.

A Non-Example: Problems NOT in P (Probably)

Here are some famous problems that are NOT known to be in P:

Notice that the best algorithms for NP-complete problems all have exponential running times (base > 1 raised to the n power). Research improves the base (from 2 down to 1.3, etc.) but never eliminates the exponential.

Chapter 2: The Class NP

Here is a puzzle. I claim this graph has a Hamiltonian cycle — a cycle that visits every vertex exactly once. Finding such a cycle might take forever. But if I HAND YOU the cycle, you can CHECK it instantly: verify that every vertex appears exactly once, and that each consecutive pair is connected by an edge. That takes O(V) time. Linear.

This asymmetry — hard to find, easy to check — is the defining feature of NP.

Certificates and Verifiers

A certificate (also called a witness) is a proposed proof that the answer is YES. For Hamiltonian Cycle, the certificate is the cycle itself — a sequence of vertices. For SAT, the certificate is a truth assignment. For CLIQUE, the certificate is the set of vertices in the clique.

A verifier is an algorithm that takes an input AND a certificate, and checks in polynomial time whether the certificate proves the answer is YES. Formally: V(x, c) runs in time polynomial in |x| and outputs YES or NO.

NP stands for Nondeterministic Polynomial time. The name comes from an equivalent definition: a nondeterministic Turing machine (one that can "guess" the certificate and then verify it) accepts the language in polynomial time. But the certificate/verifier definition is much more intuitive.

Examples

In every case, the certificate is SHORT (polynomial in input size) and the verification is FAST (polynomial time). That is all NP requires.

P ⊆ NP

Every problem in P is also in NP. Why? If you can SOLVE the problem in polynomial time, you can certainly VERIFY a certificate — just ignore the certificate and solve it yourself. The certificate is unnecessary when you can compute the answer directly. So P is a subset of NP.

The billion-dollar question is whether P is a PROPER subset. Are there problems in NP that are NOT in P? Most people believe yes, but no proof exists.

What About NO Answers?

NP only requires that YES answers have short proofs. What about NO answers? If a graph does NOT have a Hamiltonian cycle, how do you prove that? You would need to show that EVERY possible ordering of vertices fails — but there are n! orderings. A short proof of non-existence is not obviously possible.

This asymmetry gives rise to the class co-NP: problems where NO answers have short, efficiently checkable proofs. For example, "is this number composite?" is in co-NP because a NO answer (the number is prime) can be verified with a primality certificate. Interestingly, primality testing is in BOTH NP and co-NP — and it turned out to be in P as well (AKS, 2002).

Whether NP = co-NP is another open question. Most experts believe they are different. If NP ≠ co-NP, then NP-complete problems cannot have short proofs for NO answers, which would mean P ≠ NP (because P is closed under complement — if you can solve a problem in P, you can solve its complement in P, so P ⊆ NP ∩ co-NP).

The Nondeterministic Machine Interpretation

The name "NP" comes from an alternate, equivalent definition. Imagine a machine that can "guess" — at each step, it can branch into multiple paths simultaneously (nondeterministic). A nondeterministic Turing machine solves a problem if at least one branch accepts. L ∈ NP if there is a nondeterministic Turing machine that decides L in polynomial time (measuring along any single branch).

The "guess" is exactly the certificate. The nondeterministic machine guesses the certificate and then verifies it deterministically. This definition is equivalent to the verifier definition, but less intuitive. The verifier definition is what you should use in practice and in interviews.

A Subtle Point: Certificate Size

The certificate must have polynomial size relative to the input. This is a crucial requirement. If we allowed exponentially long certificates, every decidable problem would be in NP (just let the certificate encode the entire computation).

For all the NP-complete problems we study, the certificate is clearly polynomial: a truth assignment has n bits, a subset has at most n elements, a tour has exactly n cities. But some problems have certificates whose polynomial boundedness is less obvious. For example, for INTEGER PROGRAMMING, the certificate is a feasible solution — and it can be shown (non-trivially) that if an integer program is feasible, it has a solution whose bit length is polynomial in the input size.

Problems where certificates are NOT known to be polynomial-size are generally not in NP. For instance, "does this game have a winning strategy?" may require an exponentially long strategy description as a certificate, placing such problems in PSPACE rather than NP.

Chapter 3: Polynomial Reductions

Suppose you have a machine that solves problem B. Can you use it to solve problem A? If yes — if you can TRANSFORM any instance of A into an instance of B such that the answers match — then A is "no harder than" B. This transformation is called a reduction.

Formal Definition

We say A is polynomial-time reducible to B, written A ≤_P B, if there exists a polynomial-time function f such that for every instance x:

In words: f transforms a YES-instance of A into a YES-instance of B, and a NO-instance of A into a NO-instance of B. The transformation itself must run in polynomial time.

A Concrete Example: Independent Set ≤_P Vertex Cover

An independent set of size k in a graph G = (V, E) is a set of k vertices with no edges between them. A vertex cover of size j is a set of j vertices that touches every edge.

Here is the reduction: S is an independent set of size k if and only if V \ S (the remaining vertices) is a vertex cover of size |V| - k.

Proof. If S is an independent set, then no edge has both endpoints in S. So every edge has at least one endpoint in V \ S. That is exactly what "vertex cover" means. Conversely, if V \ S is a vertex cover, then every edge is touched by V \ S, so no edge lives entirely inside S, making S independent.

The transformation: given an instance (G, k) of INDEPENDENT-SET, output (G, |V| - k) as an instance of VERTEX-COVER. This takes O(1) extra work (just compute |V| - k). The answer is YES for one if and only if it is YES for the other.

Reduction as a Tool

Reductions serve two purposes:

Positive use: If you know how to solve B, reduce A to B to solve A. Example: reduce bipartite matching to max-flow. This is incredibly powerful in practice — instead of designing a new algorithm from scratch, transform your problem into a well-solved one and use an existing solver.

Negative use: If you know A is hard, reduce A to B to prove B is hard. Example: if INDEPENDENT-SET is hard, then VERTEX-COVER is hard (because we just showed INDEPENDENT-SET ≤_P VERTEX-COVER).

Reductions are the Swiss Army knife of theoretical computer science. They let you relate problems that look completely different on the surface. Boolean formulas and graphs. Number theory and scheduling. Logic and geometry. If you can build a bridge between them via a polynomial-time transformation, their complexity is linked forever.

What Makes a Good Reduction?

A reduction from A to B must satisfy three properties:

1. Polynomial-time computability. The transformation f must run in polynomial time. Otherwise, the reduction does not preserve the polynomial/exponential boundary.

2. Correctness (⇒). If x is a YES-instance of A, then f(x) is a YES-instance of B.

3. Correctness (⇐). If f(x) is a YES-instance of B, then x is a YES-instance of A. (Equivalently: if x is a NO-instance of A, then f(x) is a NO-instance of B.)

Both directions are essential. Proving only one direction gives you a one-way implication, not an equivalence. A common mistake in homework and interviews is proving only the forward direction.

Another Example: HAMILTONIAN-CYCLE ≤_P TSP

Suppose you have a magic box that solves TSP (the decision version: is there a tour of cost ≤ k?). Can you use it to solve HAMILTONIAN-CYCLE?

Yes. Given a graph G = (V, E), construct a complete weighted graph G' on the same vertices. For every edge in E, set its weight to 1. For every non-edge, set its weight to 2. Now ask TSP: "Is there a tour in G' with cost ≤ |V|?"

A tour of cost exactly |V| must use |V| edges of weight 1 — meaning it uses only edges from the original graph G. Such a tour visits all vertices exactly once using only original edges. That is a Hamiltonian cycle in G.

The construction takes O(V²) time. The answer is preserved (YES ⇔ YES). So HAMILTONIAN-CYCLE ≤_P TSP. If TSP were in P, so would HAMILTONIAN-CYCLE.

Transitivity

If A ≤_P B and B ≤_P C, then A ≤_P C. Why? Compose the two transformations. Each is polynomial, and a polynomial of a polynomial is still a polynomial. This transitivity is what makes the reduction framework so powerful — hardness propagates through chains of reductions.

This is exactly how the NP-completeness web works: Cook proved SAT is hard. Karp reduced SAT to 3-SAT, 3-SAT to CLIQUE, CLIQUE to VERTEX-COVER, and so on. Each new reduction transfers the hardness of SAT to another problem. Today, thousands of problems are known to be NP-complete, all connected by chains of polynomial-time reductions.

Common Mistakes with Reductions

Another common mistake: reducing the WRONG direction of the if-and-only-if. The reduction must map YES instances to YES instances AND NO instances to NO instances. If it only works one way, it is not a valid reduction.

Chapter 4: NP-Completeness

Now we have the pieces to define the most important concept in complexity theory.

The Definition

A problem L is NP-complete if:

Condition 2 says that L is at least as hard as EVERY problem in NP. If you could solve L in polynomial time, you could solve EVERY NP problem in polynomial time (by reducing to L first). That would mean P = NP.

A problem satisfying only condition 2 (hard, but not necessarily in NP) is called NP-hard. NP-complete = NP-hard + in NP.

Cook-Levin Theorem (1971)

The definition has a chicken-and-egg problem: to prove L is NP-complete, you must reduce EVERY NP problem to L. That requires an existing NP-complete problem to reduce from — unless you are the first.

Stephen Cook (1971) and Leonid Levin (independently, 1973) proved the first NP-complete problem exists by brute force: they showed that SAT (Boolean Satisfiability) is NP-complete by directly simulating the computation of any polynomial-time verifier as a Boolean formula.

The idea: any NP problem has a polynomial-time verifier V(x, c). A Turing machine executing V can be encoded as a Boolean formula φ whose variables represent the machine's tape cells, head position, and state at each time step. The formula φ is satisfiable if and only if there exists a certificate c that makes V accept. This construction is polynomial in the input size and the verifier's running time.

Why Cook-Levin Matters

Cook's proof is remarkable because it requires NO other NP-complete problem to exist first. It goes directly from the definition of NP to the NP-completeness of SAT. The argument has three key steps:

Step 1: Encode the Turing machine as variables. For a verifier V that runs in time T(n) on input x with certificate c, create Boolean variables for: (a) the tape contents at each cell at each time step, (b) the head position at each time step, and (c) the machine state at each time step. This gives O(T(n)²) variables.

Step 2: Encode the transition function as clauses. The Turing machine's behavior is deterministic (once you fix the certificate). Each step of the computation corresponds to a set of CNF clauses that enforce: (a) at most one state per time step, (b) the tape is updated correctly based on the transition function, (c) the head moves according to the rules. This generates polynomially many clauses.

Step 3: Encode acceptance. Add clauses requiring the machine to reach an accepting state. The resulting formula φ is satisfiable if and only if there exists a certificate c that makes V accept x. The formula has polynomial size because V runs in polynomial time.

The beauty: this construction works for ANY NP verifier. It does not care what problem V solves — it mechanically translates computation into logic. This universality is what makes SAT NP-complete.

The Domino Effect

Once Cook proved SAT is NP-complete, every subsequent NP-completeness proof became easier. To prove a NEW problem L is NP-complete, you only need to:

Richard Karp (1972) used this strategy to prove 21 problems NP-complete in one paper, starting from SAT. That paper created the landscape of NP-completeness we know today. Here are Karp's original 21 (grouped by reduction chain):

Today, Garey and Johnson's book "Computers and Intractability" (1979) catalogs over 300 NP-complete problems, and thousands more have been proven since. Every one links back to SAT through a chain of polynomial-time reductions.

Chapter 5: Key NP-Complete Problems

Every computer scientist should know the "greatest hits" of NP-complete problems. These appear constantly in interviews, research, and practice. For each one, you need to know: what it asks, what the certificate is, and what reduces to it.

SAT (Boolean Satisfiability)

Given a Boolean formula φ in conjunctive normal form (CNF) — an AND of OR-clauses — is there a truth assignment that makes φ true?

Certificate: a truth assignment. Verification: evaluate the formula, O(n). Status: the FIRST NP-complete problem (Cook-Levin, 1971).

3-SAT

Same as SAT, but every clause has EXACTLY 3 literals. This restriction does not make it easier — 3-SAT is still NP-complete (reduce from SAT by splitting long clauses). 3-SAT is the most common starting point for reductions because its structure is simple and rigid.

Note: 2-SAT (clauses with exactly 2 literals) IS in P. You can solve it in O(V + E) using the implication graph and strongly connected components. The jump from 2 to 3 literals crosses the P/NP boundary. This is a stunning example of how a tiny structural change — one more literal per clause — catapults a problem from polynomial to (almost certainly) intractable.

How does the SAT → 3-SAT reduction work? Take a long clause (l₁ ∨ l₂ ∨ ... ∨ l_k) with k > 3 literals. Introduce k-3 new variables y₁, ..., y_k-3 and replace the long clause with:

For a clause with only 1 or 2 literals, pad with dummy variables: (l₁) becomes (l₁ ∨ y ∨ z) ∧ (l₁ ∨ y ∨ ¬z) ∧ (l₁ ∨ ¬y ∨ z) ∧ (l₁ ∨ ¬y ∨ ¬z). All four clauses are satisfied if and only if l₁ is true, regardless of y and z.

CLIQUE

Given a graph G and an integer k, does G contain a clique (complete subgraph) of size k? A clique is a group of vertices where EVERY pair is connected by an edge — everyone knows everyone.

Certificate: the set of k vertices. Verification: check all k(k-1)/2 pairs are edges, O(k²). Reduced from: 3-SAT (the construction we work through in Chapter 6).

Real-world CLIQUE instances: finding groups of mutual friends in a social network, identifying cliques in protein interaction networks, and finding groups of mutually compatible components in hardware design.

Note: if k is a CONSTANT (say, k=5), then CLIQUE is in P — just check all C(n,5) = O(n⁵) possible subsets. The problem becomes hard when k is part of the input (e.g., "is there a clique of size n/2?").

VERTEX-COVER

Given a graph G and an integer k, is there a set of k vertices that touches every edge? That is, every edge in the graph has at least one endpoint in the cover set.

Certificate: the set of k vertices. Verification: check every edge has at least one endpoint in the set, O(E). Reduced from: CLIQUE (via the complement graph: G has a clique of size k ⇔ complement of G has an independent set of size k ⇔ complement of G has a vertex cover of size n-k).

Vertex cover is one of the most practically important NP-complete problems. It appears in facility location (which facilities serve all clients?), network monitoring (which routers to monitor to see all traffic?), and bioinformatics (minimum set of drugs to cover all disease pathways).

Vertex cover has a famous 2-approximation: repeatedly pick an uncovered edge, add BOTH endpoints, remove all covered edges. This greedy algorithm uses at most 2× the minimum number of vertices, runs in O(E), and is nearly the best we can achieve — improving the factor below 2 is a major open problem.

INDEPENDENT-SET

Given a graph G and an integer k, is there a set of k vertices with no edges between them? In other words, can you select k vertices that are all strangers to each other?

Certificate: the set of k vertices. Verification: check no pair is an edge, O(k²). Equivalent to VERTEX-COVER: S is an independent set ⇔ V \ S is a vertex cover. (We proved this in Chapter 3.)

Real-world instances: scheduling (select maximum non-conflicting tasks), wireless channel allocation (select non-interfering transmitters), and compiler optimization (register allocation).

HAMILTONIAN-CYCLE

Does the graph contain a cycle that visits every vertex exactly once? This is the graph-theoretic core of the Traveling Salesman Problem.

Certificate: the cycle (sequence of vertices). Verification: check all n vertices appear exactly once, and that each consecutive pair (including last-to-first) is connected by an edge. O(V) time. Reduced from: VERTEX-COVER.

Contrast with Eulerian Circuit (visiting every EDGE exactly once), which is in P — just check that every vertex has even degree. Visiting every vertex once is NP-complete; visiting every edge once is polynomial. This is one of the starkest P/NP-complete boundary examples.

TSP (Decision Version)

Given a weighted complete graph and a budget k, is there a tour visiting all vertices with total weight ≤ k?

Certificate: the tour. Verification: sum the weights and check ≤ k. O(V) time. Reduced from: HAMILTONIAN-CYCLE — given a graph G, create a complete graph where edges in G have weight 1 and non-edges have weight 2. Set budget k = |V|. A Hamiltonian cycle in G corresponds to a tour of cost |V| in the complete graph.

TSP is perhaps the most studied optimization problem in all of computer science. The best exact algorithm (Held-Karp, 1962) runs in O(2ⁿ · n²) using dynamic programming on subsets — better than n! but still exponential. The best approximation for metric TSP is Christofides' algorithm (1976): a 1.5-approximation using MST + minimum matching.

SUBSET-SUM

Given a set of integers S = {s₁, ..., s_n} and a target T, is there a subset of S that sums to exactly T?

Certificate: the subset. Verification: sum the elements and check = T. O(n) time. Reduced from: 3-SAT (using a clever "gadget" construction where each variable and clause contributes digits to large numbers).

SUBSET-SUM has a fascinating pseudo-polynomial algorithm: dynamic programming in O(nT) time. This is NOT polynomial in the INPUT SIZE because T can be exponentially large when encoded in binary (log₂(T) bits). But when T is small (say, polynomial in n), the DP is fast. This is called pseudo-polynomial time, and it is the reason why real-world knapsack/subset-sum instances are often tractable despite being NP-complete.

GRAPH-COLORING (k ≥ 3)

Can the graph's vertices be colored with k colors so no adjacent vertices share a color?

Certificate: the coloring (a color for each vertex). Verification: check each edge, O(E). Reduced from: 3-SAT.

2-coloring is in P — it is equivalent to checking bipartiteness with BFS in O(V + E). 3-coloring is NP-complete. Again, the jump from 2 to 3 crosses the P/NP-complete boundary.

Graph coloring has direct applications: register allocation in compilers (colors = registers, edges = variables alive simultaneously), scheduling (colors = time slots, edges = conflicts), and frequency assignment in cellular networks (colors = frequencies, edges = interference).

The Reduction Roadmap

Understanding which problem reduces to which is crucial for NP-completeness proofs. Here is the standard chain, showing how hardness propagates:

The key insight: when you see a new problem, find the CLOSEST known NP-complete problem in this roadmap and reduce from it. The closer the structural match, the simpler the reduction.

Pseudo-Polynomial Time: A Subtlety

Several NP-complete problems have algorithms that LOOK polynomial but technically are not. These are called pseudo-polynomial algorithms:

Problems with pseudo-polynomial algorithms are called weakly NP-complete. Problems WITHOUT pseudo-polynomial algorithms (like 3-SAT, CLIQUE, TSP) are called strongly NP-complete. The distinction matters in practice: weakly NP-complete problems are often tractable when the numbers involved are small.

python
def subset_sum_dp(nums, target):
    """Pseudo-polynomial DP for SUBSET-SUM.
    Time: O(n * target). Space: O(target).
    Only practical when target is not astronomically large."""
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        # Iterate backwards to avoid using same element twice
        for j in range(target, num - 1, -1):
            if dp[j - num]:
                dp[j] = True
    return dp[target]

# Example
print(subset_sum_dp([3, 7, 1, 8, 4], 11))  # True: 3+8=11
print(subset_sum_dp([3, 7, 1, 8, 4], 20))  # True: 3+7+1+8+4-3=20 wait, 3+7+1+8+4=23, hmm. True: 7+1+8+4=20

The Verification Asymmetry

Look at the pattern across all these problems. In every case:

Certificate size: polynomial in the input. A truth assignment has n bits. A clique listing has k vertices. A tour has V edges. The proposed solution is SHORT.

Verification time: polynomial. Evaluate the formula. Check all pairs. Sum the weights. Verification is FAST.

Search space: exponential. 2ⁿ truth assignments. C(V, k) subsets. (V-1)!/2 tours. FINDING the certificate means searching this space.

This asymmetry — short, checkable certificates sitting in exponentially large search spaces — is the essence of NP. The question P vs NP asks whether this asymmetry is fundamental or just an artifact of our ignorance.

Chapter 6: Proving NP-Completeness

This is the most important practical skill in complexity theory. Given a new problem, how do you prove it is NP-complete?

The Recipe

Worked Example: 3-SAT ≤_P CLIQUE

We will prove CLIQUE is NP-complete by reducing 3-SAT to it. This is one of Karp's original 21 reductions.

Step 1: CLIQUE ∈ NP. Certificate: a set S of k vertices. Verifier: check |S| = k, then check all k(k-1)/2 pairs are edges. Time: O(k²) ≤ O(V²). Done.

Step 2: Reduce from 3-SAT.

Step 3: The construction. Given a 3-SAT formula with m clauses, each containing 3 literals, build a graph G as follows:

For each clause C_i = (l_i1 ∨ l_i2 ∨ l_i3), create 3 vertices — one for each literal in the clause. Call them v_i1, v_i2, v_i3.

Connect two vertices v_ij and v_kl with an edge if and only if: (a) they are in DIFFERENT clauses (i ≠ k), AND (b) they are not contradictory (v_ij ≠ ¬v_kl).

Set the clique size target to k = m (number of clauses).

Step 4: Correctness.

(⇒) If the formula is satisfiable, pick one TRUE literal from each clause. The corresponding m vertices form a clique: they are in different clauses (so condition (a) is met), and they are all simultaneously true (so no two are contradictory, meeting condition (b)).

(⇐) If G has a clique of size m, it contains exactly one vertex from each clause (since vertices within the same clause have no edges). Set each selected literal to TRUE. This is consistent (no contradictions, because contradictory literals have no edge). Each clause has a true literal, so the formula is satisfied.

Step 5: Time. Creating 3m vertices and at most O(m²) edges. Polynomial in the formula size.

Hand-Traced Example

Let us walk through the 3-SAT → CLIQUE reduction step by step with a concrete instance.

The beauty of this reduction: the graph's structure perfectly encodes the logical constraints of the formula. No edges within a clause forces one-per-clause selection. No edges between contradictory literals forces consistency. A clique of size m IS a satisfying assignment, and vice versa.

Second Worked Example: VERTEX-COVER ≤_P INDEPENDENT-SET

This is a much simpler reduction that shows how complements work.

Step 1: INDEPENDENT-SET ∈ NP. Certificate: a set S of k vertices. Verifier: check |S| = k, then check that for every pair u, v ∈ S, (u, v) is NOT an edge. Time: O(k²).

Step 2: Reduce VERTEX-COVER. Given an instance (G, k) of VERTEX-COVER (does G have a vertex cover of size k?), output (G, |V| - k) as an instance of INDEPENDENT-SET.

Step 3 (⇒): If G has a vertex cover C of size k, then V \ C is an independent set of size |V| - k. Proof: if two vertices u, v are both in V \ C, then neither is in the cover, so the edge (u,v) cannot exist (otherwise the cover would miss it). So V \ C has no internal edges — it is independent.

Step 4 (⇐): If G has an independent set S of size |V| - k, then V \ S is a vertex cover of size k. Proof: every edge has at least one endpoint outside S (since S has no edges), meaning at least one endpoint in V \ S.

Step 5: Time. The transformation is trivial — just compute |V| - k. O(1).

This reduction is beautifully simple. It shows that VERTEX-COVER and INDEPENDENT-SET are essentially the same problem viewed from opposite sides. A set of "selected" vertices is simultaneously an independent set (when viewed internally — no edges) and the complement of a vertex cover (when viewed externally — all edges touched).

Third Worked Example: 3-SAT ≤_P INDEPENDENT-SET

This reduction is more complex and shows how logical constraints translate to graph structure. It is an alternative to the 3-SAT → CLIQUE reduction (they are closely related — CLIQUE and INDEPENDENT-SET are complements).

Construction: Given a 3-SAT formula with m clauses:

1. For each clause, create a triangle (3 vertices connected in a cycle) — one vertex per literal.

2. Add "conflict edges" between vertices representing contradictory literals (x_i and ¬x_i).

3. Ask: does this graph have an independent set of size m?

An independent set of size m cannot pick two vertices from the same triangle (they are connected), so it picks exactly one from each. The conflict edges prevent picking both x_i and ¬x_i, ensuring consistency. The selected literals form a satisfying assignment.

Choosing Which Problem to Reduce From

Chapter 7: Coping with NP-Completeness

You have proven your problem is NP-complete. Now what? Give up? Of course not. You have four strategies, each with different tradeoffs.

Strategy 1: Approximation Algorithms

Accept a solution that is CLOSE to optimal rather than exactly optimal. For many NP-complete problems, you can guarantee a solution within a constant factor of optimal in polynomial time.

Example: the 2-approximation for Vertex Cover. Repeatedly pick an uncovered edge, add BOTH endpoints to the cover, and remove all edges incident to them. This runs in O(E) time and uses at most 2× the optimal number of vertices. (The optimal cover must include at least one endpoint of each edge we picked, and we included both — so at most 2×.)

Let us see the 2-approximation in action. The algorithm is stunningly simple:

python
def approx_vertex_cover(graph):
    """2-approximation for minimum vertex cover.
    Repeatedly pick an uncovered edge, add BOTH endpoints.
    Returns at most 2 × OPT vertices."""
    cover = set()
    edges = set(graph.edges())
    while edges:
        u, v = edges.pop()  # pick any uncovered edge
        cover.add(u)
        cover.add(v)
        # remove all edges incident to u or v
        edges = {(a, b) for a, b in edges
                 if a != u and a != v and b != u and b != v}
    return cover

Why is this a 2-approximation? The algorithm selects a set of DISJOINT edges (a matching). The optimal cover must include at least one endpoint of each edge in the matching. We include both endpoints. So we use at most 2 × |matching| ≤ 2 × OPT vertices.

Strategy 2: Special Cases

Many NP-complete problems become easy for restricted input classes:

Strategy 3: Exact but Smart

Use exponential-time algorithms that are smarter than brute force. The goal is to reduce the base of the exponential (from n! down to 2ⁿ) using clever algorithmic techniques.

Dynamic Programming on subsets (Held-Karp). For TSP, instead of checking all n! tours, observe that the cost of an optimal tour through a SUBSET of cities depends only on which cities are in the subset and which city is the last one visited. This gives the recurrence:

Where S is a bitmask representing the set of visited cities and j is the current city. There are 2ⁿ · n states and each takes O(n) to compute, giving O(2ⁿ · n²) total time. For n = 20, this is about 400 million — feasible! Compare to 20! = 2.4 × 10¹⁸ for brute force.

Branch-and-bound. Explore the search tree systematically but PRUNE branches that cannot possibly lead to an optimal solution. For TSP: compute a lower bound on the remaining tour cost (e.g., using MST of unvisited cities). If current cost + lower bound ≥ best known solution, abandon this branch. In practice, this can solve instances with 20-40 cities in seconds.

Backtracking with constraint propagation. For SAT, the DPLL algorithm (Davis-Putnam-Logemann-Loveland, 1962) combines backtracking with two powerful propagation rules: (1) unit propagation — if a clause has only one unassigned literal, that literal must be true; (2) pure literal elimination — if a variable appears only positively (or only negatively), set it accordingly. Modern SAT solvers add conflict-driven clause learning (CDCL): when a conflict is found, learn a new clause that prevents the same mistake, and backjump to the relevant decision point. CDCL solvers routinely solve instances with millions of variables.

Strategy 4: Heuristics and Metaheuristics

No guarantee of optimality or approximation ratio, but works well in practice. These methods are essential when the input is too large for exact methods and too unstructured for approximation algorithms.

Local search. Start with any feasible solution. Repeatedly make small changes (the "neighborhood") that improve the objective. Stop when no neighbor is better. 2-opt and 3-opt for TSP are local search algorithms. Problem: can get stuck in local optima.

Simulated annealing. Like local search, but sometimes accepts WORSE moves (with probability e^-Δ/T) to escape local optima. The "temperature" T decreases over time, so the algorithm accepts fewer bad moves as it progresses. Inspired by the physical process of cooling metal (annealing).

Genetic algorithms. Maintain a POPULATION of solutions. In each generation: (1) select the fittest solutions, (2) "crossover" pairs to produce offspring, (3) "mutate" randomly. Over many generations, the population evolves toward good solutions. Works well for combinatorial optimization but requires careful tuning.

Tabu search. Local search with a memory. Maintain a "tabu list" of recent moves and forbid reversing them. This forces the search to explore new regions instead of cycling. Effective for scheduling and graph coloring.

Try it with 10 cities first — brute force completes quickly and you can see that simulated annealing finds the same (or very close) tour. Now try 15 — brute force takes noticeably longer while the heuristics finish instantly. At 18 cities, brute force explores 17! / 2 ≈ 177 billion tours and may not finish within your patience threshold, while nearest neighbor + 2-opt still produces a good tour in milliseconds.

Understanding the Results

What you should observe from the simulation:

Nearest neighbor is fast but often bad. It makes greedy choices — always going to the closest unvisited city — which can leave long "cleanup" edges at the end. Typical quality: 1.2-1.5x optimal for random instances.

2-opt consistently improves on nearest neighbor by uncrossing edges. It starts from the greedy tour and locally optimizes until no single swap helps. Typical quality: 1.05-1.15x optimal. This is remarkably good for such a simple algorithm.

Simulated annealing sometimes beats 2-opt by escaping local optima. The random perturbation with temperature-dependent acceptance allows it to explore more of the solution space. But it is stochastic — run it twice and you may get different answers.

Brute force always finds the optimal solution. But its running time grows as (n-1)!/2, which is about 3.6 million for n=10, 43 billion for n=15, and 64 quadrillion for n=20. It is the only algorithm that gives a GUARANTEE of optimality.

The 2-opt Algorithm

2-opt is the simplest and most powerful local search for TSP. The idea: if two edges in the tour CROSS, you can "uncross" them to get a shorter tour. Specifically: take two edges (a,b) and (c,d), remove them, and reconnect as (a,c) and (b,d) by reversing the segment between b and c. Repeat until no improvement is possible.

python
def two_opt(tour, dist):
    """Improve tour by uncrossing edges."""
    n = len(tour)
    improved = True
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                # Cost of current edges vs swapped
                d1 = dist[tour[i-1]][tour[i]] + dist[tour[j]][tour[(j+1)%n]]
                d2 = dist[tour[i-1]][tour[j]] + dist[tour[i]][tour[(j+1)%n]]
                if d2 < d1:
                    tour[i:j+1] = tour[i:j+1][::-1]  # reverse segment
                    improved = True
    return tour

The Held-Karp DP for TSP

The Held-Karp algorithm (1962) is the gold standard for exact TSP on small instances. It exploits the observation that the optimal tour through a subset S of cities, ending at city j, depends ONLY on S and j — not on the order in which the other cities in S were visited.

Let dp[S][j] = minimum cost to start at city 0, visit all cities in S (a bitmask), and end at city j. The recurrence:

Base case: dp[{j}, j] = dist(0, j) for each city j ≠ 0.

Final answer: min_j { dp[all cities, j] + dist(j, 0) }.

The number of subsets is 2ⁿ. For each subset, we consider n possible ending cities. For each (subset, ending city) pair, we try n-1 predecessors. Total: O(2ⁿ · n²).

For n = 20: about 400 million operations (a few seconds). For n = 25: about 25 billion (a few hours). For n = 30: about 30 trillion (impractical). This is vastly better than 20! ≈ 2.4 × 10¹⁸, but still exponential.

python
def held_karp(dist):
    """Exact TSP via DP on subsets. O(2^n * n^2).
    dist: n×n distance matrix. Returns optimal tour cost."""
    n = len(dist)
    # dp[mask][j] = min cost to visit cities in mask, ending at j
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]

    # Base: start at city 0, go to city j
    for j in range(1, n):
        dp[1 << j][j] = dist[0][j]

    # Fill DP table by increasing subset size
    for mask in range(1, 1 << n):
        for j in range(1, n):
            if not (mask & (1 << j)): continue
            prev_mask = mask ^ (1 << j)  # mask without j
            if prev_mask == 0: continue
            for k in range(1, n):
                if not (prev_mask & (1 << k)): continue
                if dp[prev_mask][k] + dist[k][j] < dp[mask][j]:
                    dp[mask][j] = dp[prev_mask][k] + dist[k][j]

    # Find min cost to visit all cities and return to 0
    full_mask = (1 << n) - 2  # all cities except 0
    return min(dp[full_mask][j] + dist[j][0] for j in range(1, n))

# Compare scaling:
# n=15: Brute force = 15!/2 ≈ 653B  |  Held-Karp = 2^15 × 15^2 ≈ 7.4M
# n=20: Brute force = 20!/2 ≈ 1.2E18  |  Held-Karp = 2^20 × 400 ≈ 419M
# n=25: Brute force = 25!/2 ≈ 7.8E24  |  Held-Karp = 2^25 × 625 ≈ 21B

Simulated Annealing

Like 2-opt, but sometimes accepts WORSE moves to escape local optima. The probability of accepting a worse move decreases over time (the "temperature" cools). Early on, the algorithm explores widely. Later, it settles into a good region. This is a metaheuristic — a general-purpose framework that works for many different optimization problems.

python
import random, math

def simulated_annealing(tour, dist, T=1000, cooling=0.995, min_T=1e-8):
    def cost(t):
        return sum(dist[t[i]][t[(i+1)%len(t)]] for i in range(len(t)))

    best = tour[:]
    best_cost = cost(best)
    curr = tour[:]
    curr_cost = best_cost

    while T > min_T:
        # Random 2-opt swap
        i, j = sorted(random.sample(range(len(curr)), 2))
        new = curr[:]
        new[i:j+1] = new[i:j+1][::-1]
        new_cost = cost(new)

        delta = new_cost - curr_cost
        if delta < 0 or random.random() < math.exp(-delta / T):
            curr, curr_cost = new, new_cost
            if curr_cost < best_cost:
                best, best_cost = curr[:], curr_cost
        T *= cooling
    return best

Summary: Decision Matrix

When faced with an NP-hard problem in practice, use this decision tree:

Also check for special cases. Is the graph planar? Sparse? Bipartite? Does the problem have bounded treewidth? A special structure? Many NP-hard problems become polynomial on restricted inputs. This is where domain knowledge pays off.

Coding Drill: Greedy Graph Coloring

While optimal k-coloring is NP-hard for k ≥ 3, a simple greedy algorithm colors any graph with at most Δ + 1 colors (where Δ is the maximum degree). This is not optimal but always polynomial.

python
def greedy_coloring(adj):
    """Greedy graph coloring. Assigns colors 0, 1, 2, ...
    Uses at most max_degree + 1 colors.
    adj: adjacency list (dict of sets)."""
    color = {}
    for node in adj:
        # Colors used by neighbors
        used = {color[nb] for nb in adj[node] if nb in color}
        # Assign smallest available color
        c = 0
        while c in used:
            c += 1
        color[node] = c
    return color

# Example: Petersen graph (chromatic number = 3)
petersen = {
    0: {1,4,5}, 1: {0,2,6}, 2: {1,3,7},
    3: {2,4,8}, 4: {3,0,9}, 5: {0,7,8},
    6: {1,8,9}, 7: {2,5,9}, 8: {3,5,6},
    9: {4,6,7}
}
result = greedy_coloring(petersen)
print(max(result.values()) + 1, "colors used")  # 3 or 4

The greedy approach uses at most Δ + 1 colors. For the Petersen graph (Δ = 3), it uses 3 or 4 colors depending on vertex ordering. The optimal is 3. Better orderings (like Welsh-Powell: sort by degree descending) tend to use fewer colors.

Chapter 8: P vs NP in Practice

We have danced around the central question. Let us confront it head-on.

The Status

P vs NP is unresolved. After more than 50 years of research, we have neither a proof that P = NP nor a proof that P ≠ NP. However, the overwhelming consensus among computer scientists is that P ≠ NP. A 2019 survey found that 88% of complexity theorists believe P ≠ NP.

What if P = NP?

If someone proved P = NP constructively (by giving an algorithm), the consequences would be staggering:

Cryptography collapses. RSA, Diffie-Hellman, and nearly all public-key cryptography rely on the assumption that factoring and discrete logarithms are hard. These problems are in NP. If P = NP, polynomial-time algorithms exist for all of them. Every encrypted message ever sent could be decrypted.

Optimization becomes trivial. Protein folding, chip design, logistics, scheduling — all solved optimally in polynomial time. Drug discovery, materials science, and operations research would be revolutionized overnight.

Proofs become findable. If a mathematical theorem has a proof of length n, finding it is an NP problem (the proof is the certificate). P = NP would mean proofs can be found efficiently. Mathematics itself would be transformed.

What if P ≠ NP?

If P ≠ NP, then NP-complete problems are fundamentally intractable. No polynomial-time algorithm exists for any of them — not because we are not clever enough, but because the problems are mathematically hard. The heuristic and approximation strategies from Chapter 7 are the best we can do.

On the positive side: cryptography is secure. Computational hardness assumptions are justified. The economy of trust that the internet runs on is safe.

The Complexity Landscape

NP-complete problems sit at a very specific point in the complexity landscape. Let us zoom out to see the bigger picture.

co-NP: Problems where NO answers have short proofs. Example: "is this formula UNSATISFIABLE?" A proof of unsatisfiability is not obviously short (you'd need to show that NO assignment works). co-NP is believed to be different from NP.

NP-hard: At least as hard as NP-complete, but not necessarily in NP. This includes optimization versions (finding the shortest tour, not just deciding if one exists with cost ≤ k) and problems that are even HARDER than NP-complete (like the halting problem, which is undecidable).

PSPACE: Problems solvable with polynomial SPACE (but possibly exponential time). Includes all of NP. Example: Quantified Boolean Formula (QBF) — SAT with universal and existential quantifiers — is PSPACE-complete.

EXP: Problems solvable in exponential time. Contains PSPACE, which contains NP, which contains P. Whether any of these containments are strict is open.

Quantum Computing and NP

A common misconception: "quantum computers will solve NP-complete problems efficiently." This is almost certainly false. Quantum computers define their own complexity class, BQP (Bounded-error Quantum Polynomial time). The current best understanding is:

P ⊆ BQP ⊆ PSPACE, and most experts believe NP ¬⊆ BQP — meaning quantum computers cannot solve NP-complete problems in polynomial time.

What quantum computers CAN do efficiently: factor integers (Shor's algorithm — breaks RSA), search unsorted databases (Grover's algorithm — quadratic speedup, O(√N) instead of O(N)), and simulate quantum systems. Shor's algorithm is why factoring is a special case: it is in NP, not known to be NP-complete, and solvable in quantum polynomial time. The quantum world might shrink the gap between P and NP, but it does not close it.

NP-Completeness in the Real World

Despite theoretical intractability, NP-complete problems are solved "well enough" every day in industry:

SAT solvers (DPLL + CDCL) routinely solve instances with millions of variables in seconds. The worst case is exponential, but practical instances have structure that solvers exploit. SAT solvers verify hardware, solve scheduling, and even prove mathematical theorems.

Integer Linear Programming (ILP) solvers like Gurobi and CPLEX solve NP-hard optimization problems with thousands of variables by combining branch-and-bound, cutting planes, and heuristics. Supply chain optimization, airline scheduling, and financial portfolio optimization all rely on ILP.

TSP instances with tens of thousands of cities have been solved optimally using branch-and-cut algorithms. The record is over 85,000 cities (a VLSI circuit layout). For larger instances, the LKH heuristic finds solutions within 1% of optimal.

The lesson: worst-case exponential does not mean every-case exponential. Theory tells you when to be wary; practice tells you when to be hopeful.

The Fine-Grained Complexity Perspective

Modern complexity theory goes beyond "polynomial vs exponential." Fine-grained complexity asks: WHICH polynomial? WHICH exponential? The key conjecture is the Strong Exponential Time Hypothesis (SETH): for every ε > 0, there exists a k such that k-SAT cannot be solved in O(2^(1-ε)n) time.

SETH has far-reaching consequences. If SETH is true:

This means even problems IN P might have tight complexity barriers. The polynomial world is not uniformly easy — some polynomial-time problems might be stuck at O(n²) or O(n³) forever, with no hope of faster algorithms.

Open Problems

NP-completeness spawned an entire research ecosystem. Here are the biggest open questions:

1. P vs NP. The big one. $1M Millennium Prize. Most believe P ≠ NP.

2. NP vs co-NP. If NP ≠ co-NP, then P ≠ NP (but not vice versa). Can we at least prove NP ≠ co-NP?

3. Natural proofs barrier. Razborov and Rudich (1997) showed that a large class of "natural" proof techniques CANNOT separate P from NP if one-way functions exist. This partly explains why the problem is so hard to resolve.

4. Is graph isomorphism NP-complete? Babai (2015) showed it is in quasi-polynomial time. Most experts believe it is NOT NP-complete, making it a rare "NP-intermediate" candidate.

5. Unique Games Conjecture. Khot (2002) conjectured that a certain constraint satisfaction problem is hard to approximate. If true, it implies that many known approximation algorithms are OPTIMAL — you cannot do better unless P = NP.

Chapter 9: Interview Arsenal

NP-completeness appears in two interview contexts: theory questions ("is this problem NP-hard?") and practical questions ("this problem is NP-hard, what do you do?"). Here is everything you need for both.

The Cheat Sheet

Red Flags: When to Suspect NP-Hardness

Green Flags: When a Problem is Probably in P

When Asked "How Would You Solve This NP-Hard Problem?"

Coding Drill: Backtracking SAT with Unit Propagation

python
def dpll(clauses, assignment=None):
    """DPLL SAT solver with unit propagation.
    clauses: list of lists of ints (positive = true, negative = negated).
    Returns satisfying assignment dict or None."""
    if assignment is None: assignment = {}

    # Unit propagation: if a clause has one unassigned literal, force it
    changed = True
    while changed:
        changed = False
        for clause in clauses:
            unassigned = []
            satisfied = False
            for lit in clause:
                var = abs(lit)
                if var in assignment:
                    if (lit > 0) == assignment[var]:
                        satisfied = True; break
                else:
                    unassigned.append(lit)
            if satisfied: continue
            if len(unassigned) == 0: return None  # conflict!
            if len(unassigned) == 1:  # unit clause — force it
                lit = unassigned[0]
                assignment[abs(lit)] = lit > 0
                changed = True

    # Check if all clauses satisfied
    all_sat = True
    for clause in clauses:
        sat = any(
            abs(l) in assignment and (l > 0) == assignment[abs(l)]
            for l in clause
        )
        if not sat:
            if all(abs(l) in assignment for l in clause):
                return None  # conflict
            all_sat = False
    if all_sat: return assignment

    # Choose an unassigned variable and branch
    all_vars = {abs(l) for c in clauses for l in c}
    unassigned_vars = all_vars - set(assignment.keys())
    var = min(unassigned_vars)

    for val in [True, False]:
        new_assign = {**assignment, var: val}
        result = dpll(clauses, new_assign)
        if result is not None: return result

    return None

# Example usage
clauses = [[1, -2, 3], [-1, 2], [2, 3], [-3]]
result = dpll(clauses)
print(result)  # {3: False, 2: True, 1: True}

Coding Drill: Backtracking TSP

python
import itertools

def tsp_brute_force(dist):
    """Exact TSP via permutation enumeration. O(n!)"""
    n = len(dist)
    cities = list(range(n))
    best_cost = float('inf')
    best_tour = None
    for perm in itertools.permutations(cities[1:]):
        tour = [0] + list(perm)
        cost = sum(dist[tour[i]][tour[i+1]] for i in range(n-1))
        cost += dist[tour[-1]][tour[0]]
        if cost < best_cost:
            best_cost = cost
            best_tour = tour
    return best_tour, best_cost


def tsp_nearest_neighbor(dist):
    """Greedy heuristic. O(n^2). No optimality guarantee."""
    n = len(dist)
    visited = [False] * n
    tour = [0]
    visited[0] = True
    for _ in range(n - 1):
        last = tour[-1]
        nearest = min(
            (j for j in range(n) if not visited[j]),
            key=lambda j: dist[last][j]
        )
        tour.append(nearest)
        visited[nearest] = True
    return tour


def tsp_held_karp(dist):
    """DP over subsets. O(2^n * n^2). Much better than n!"""
    n = len(dist)
    # dp[S][i] = min cost to visit all cities in subset S, ending at i
    dp = {}
    for i in range(n):
        dp[(1 << i, i)] = dist[0][i]

    for size in range(2, n):
        for S in itertools.combinations(range(1, n), size):
            bits = 0
            for b in S: bits |= 1 << b
            for j in S:
                prev = bits ^ (1 << j)
                dp[(bits, j)] = min(
                    dp.get((prev, k), float('inf')) + dist[k][j]
                    for k in S if k != j
                )

    full = (1 << n) - 2  # all except city 0
    return min(dp.get((full, j), float('inf')) + dist[j][0] for j in range(1, n))

Five-Minute NP-Completeness Proof Template

In interviews, you may need to sketch a proof that a problem is NP-complete. Here is the template:

Practice Problem: Prove PARTITION is NP-Complete

PARTITION: Given a multiset S of integers, can S be divided into two subsets S₁, S₂ with equal sum?

Step 1: PARTITION ∈ NP. Certificate: the subset S₁. Verifier: sum S₁ and S \ S₁, check they are equal. Time: O(n).

Step 2: Reduce SUBSET-SUM to PARTITION. Given a SUBSET-SUM instance (S, T), let σ = sum of all elements in S. Create a PARTITION instance S' = S ∪ {σ - 2T}. The total sum of S' is 2σ - 2T. A partition has each half summing to σ - T. If the SUBSET-SUM has a subset summing to T, then those elements plus the new element (σ - 2T) sum to T + σ - 2T = σ - T. The remaining elements sum to σ - T. Done.

Step 3 (⇒): If SUBSET-SUM has subset A with sum(A) = T, then A ∪ {σ - 2T} has sum T + σ - 2T = σ - T, and the complement has sum σ - T. Partition exists.

Step 4 (⇐): If PARTITION exists, the half containing the new element has sum σ - T. Removing the new element gives sum σ - T - (σ - 2T) = T. This subset is a valid SUBSET-SUM solution.

Common Interview Questions

Coding Drill: 2-SAT Solver

python
from collections import defaultdict

def solve_2sat(n, clauses):
    """Solve 2-SAT in O(V+E) using implication graph + SCC.
    n = number of variables (1-indexed).
    clauses = list of (a, b) where positive = true, negative = false.
    Returns assignment list or None if unsatisfiable."""

    # Build implication graph
    # Clause (a ∨ b) = (¬a → b) ∧ (¬b → a)
    graph = defaultdict(list)
    rgraph = defaultdict(list)

    def neg(x): return -x

    for a, b in clauses:
        graph[neg(a)].append(b)
        graph[neg(b)].append(a)
        rgraph[b].append(neg(a))
        rgraph[a].append(neg(b))

    # Kosaraju's SCC
    nodes = set()
    for i in range(1, n+1):
        nodes.add(i); nodes.add(-i)

    order = []
    visited = set()
    def dfs1(u):
        stack = [(u, False)]
        while stack:
            v, done = stack.pop()
            if done: order.append(v); continue
            if v in visited: continue
            visited.add(v)
            stack.append((v, True))
            for w in graph[v]: stack.append((w, False))

    for u in nodes:
        if u not in visited: dfs1(u)

    comp = {}
    c = 0
    def dfs2(u, c):
        stack = [u]
        while stack:
            v = stack.pop()
            if v in comp: continue
            comp[v] = c
            for w in rgraph[v]: stack.append(w)

    for u in reversed(order):
        if u not in comp: dfs2(u, c); c += 1

    # Check satisfiability
    for i in range(1, n+1):
        if comp.get(i) == comp.get(-i):
            return None  # unsatisfiable

    # Assignment: x is TRUE iff comp[x] > comp[¬x]
    return [comp.get(i, 0) > comp.get(-i, 0) for i in range(1, n+1)]

Coding Drill: FPT Vertex Cover (O(2^k · n))

This algorithm finds a vertex cover of size ≤ k (or reports none exists) in O(2^k · (V + E)) time. The key insight: pick any edge (u, v). The optimal cover must include u or v (or both). Branch on both choices, reducing k by 1 each time.

python
def fpt_vertex_cover(adj, k):
    """Find vertex cover of size ≤ k using bounded search tree.
    adj: dict of sets. Returns cover set or None.
    Time: O(2^k * (V + E))."""
    if k < 0: return None

    # Find any uncovered edge
    for u in adj:
        for v in adj[u]:
            if u < v:  # found edge (u, v)
                # Branch 1: include u in cover
                adj1 = {n: (s - {u}) for n, s in adj.items() if n != u}
                result = fpt_vertex_cover(adj1, k - 1)
                if result is not None:
                    return result | {u}

                # Branch 2: include v in cover
                adj2 = {n: (s - {v}) for n, s in adj.items() if n != v}
                result = fpt_vertex_cover(adj2, k - 1)
                if result is not None:
                    return result | {v}

                return None  # neither works

    # No uncovered edges — cover is complete
    return set()

# Example
graph = {0:{1,2}, 1:{0,2,3}, 2:{0,1,3}, 3:{1,2}}
print(fpt_vertex_cover(graph, 2))  # {1, 2} — covers all edges
print(fpt_vertex_cover(graph, 1))  # None — no vertex cover of size 1

The depth of the recursion is at most k (we reduce k by 1 each level). At each level, we branch into 2 choices. So the search tree has at most 2^k leaves. Each node does O(V + E) work to find an edge and remove a vertex. Total: O(2^k · (V + E)). For k = 30 and a graph with 1 million vertices, this is about 10¹⁵ — feasible. The exponential is in the PARAMETER k, not in the graph size.

Practice: Reducing Real Problems to Known NP-Hard Ones

In interviews, you often need to recognize that a "new" problem is actually a known NP-hard problem in disguise. Here are common transformations:

Chapter 10: Connections

NP-completeness connects to nearly every area of algorithm design. Here is how this chapter links to the rest of the CLRS curriculum.

Where NP-Completeness Appears

Comparison: What Makes a Problem Hard?

The pattern is striking: tiny changes in problem formulation — one more color, one more literal per clause, visiting vertices instead of edges — can catapult a problem from trivially polynomial to NP-complete. The boundary between P and NP-complete is razor-thin.

Parameterized Complexity: A Finer View

Sometimes a problem is NP-hard in general but becomes tractable when a specific PARAMETER is small. Fixed-Parameter Tractability (FPT) studies this phenomenon:

VERTEX-COVER with parameter k is a poster child: you can solve "does this graph have a vertex cover of size ≤ k?" in O(2^k · n) time. For k = 30 and n = 10 million, this is about 10¹⁶ — feasible! The exponential is in k (which might be small), not in n (which might be large).

This is a critical distinction for practitioners. Before declaring a problem "hopeless because it's NP-hard," ask: is there a natural small parameter? If so, an FPT algorithm might save the day.

The FPT framework complements NP-completeness beautifully. NP-completeness tells you the problem is hard in general. FPT tells you WHICH aspect of the input makes it hard. If that aspect is bounded in your application, you may still have an efficient algorithm.

The hierarchy of parameterized complexity has its own classes (FPT ⊆ W[1] ⊆ W[2] ⊆ ... ⊆ XP), with conjectured separations analogous to P vs NP. CLIQUE (parameterized by k) is complete for W[1] — the parameterized analog of NP-complete. This means: if you can solve CLIQUE in FPT time, you can solve every W[1] problem in FPT time. Most experts believe this is impossible.

Historical Context

The theory of NP-completeness was born in a remarkably short period:

Approximation Algorithm Highlights

Chapter 35 of CLRS covers approximation algorithms in depth. Here is a preview of the key results:

Notice that different problems have wildly different approximability. KNAPSACK can be approximated to within (1 + ε) for any ε > 0 (a FPTAS). TSP cannot be approximated at all without the metric constraint (any constant ratio is NP-hard). VERTEX-COVER is stuck at factor 2. SET-COVER has a tight ln(n) ratio. These variations are one of the deepest aspects of complexity theory.

The Bigger Picture

NP-completeness theory gives you a framework for the most practical skill in algorithm design: knowing when to stop looking for an efficient algorithm. If you can prove your problem is NP-hard, you stop trying to find a polynomial algorithm and switch to approximation, heuristics, or special-case exploitation. This saves weeks of futile algorithmic effort.

The theory also reveals a deep structural unity: thousands of seemingly unrelated problems — from circuit design to scheduling to biology — are all computationally equivalent. Solve one, solve them all. This is one of the most beautiful results in all of mathematics and computer science.

Recommended Reading

NP-Completeness in Machine Learning

If you are in the AI/ML world, NP-completeness appears more than you might expect:

Notice the pattern: ML uses NP-complete problems everywhere, but gets away with heuristic solutions (SGD, MCMC, greedy) because (a) real-world instances have structure, and (b) approximate solutions are usually sufficient. The theory of NP-completeness explains why these heuristics sometimes fail catastrophically on pathological inputs.

Key Takeaways for Your Career

1. Recognize NP-hardness early. If you spend a week trying to find a polynomial algorithm for an NP-hard problem, that is a week wasted. Learn the red flags (Chapter 9) and check for NP-hardness before investing in algorithm design.

2. Reductions are a design tool. Even outside complexity theory, the idea of "transforming problem A into problem B" is fundamental. Reduce your problem to a well-studied one (max-flow, LP, SAT) and use an existing solver. This is how most industrial optimization works.

3. "NP-hard" is not a death sentence. It means worst-case exponential. Real instances often have structure that algorithms exploit. Try SAT solvers, ILP solvers, approximation algorithms, and heuristics before giving up. Know the special cases in P.

4. The P vs NP question is about the nature of creativity. Can FINDING a proof ever be as easy as CHECKING one? Can CREATING a solution be as easy as VERIFYING one? This is a question about the fundamental nature of intellectual effort, formalized in the language of computation.