Cook's Theorem & Reduction Techniques

50 mins

Learn the foundational theorem of complexity theory. Understand how polynomial-time reductions are used to prove NP-completeness, complete with a step-by-step trace of reducing 3-SAT to Vertex Cover.

Learning Goals

State Cook's Theorem and explain its foundational importance.
Identify the standard NP-Complete problems as defined by the syllabus.
Understand the properties and purpose of Polynomial-Time Reductions.
Trace the mathematical reduction from 3-SAT to Vertex Cover using Graph Gadgets.

Cook's Theorem

(Directly answers 2024 Q8a ii & iii)

Cook's Theorem (1971) states that the Boolean Satisfiability Problem (SAT) is NP-Complete.

Why is this a foundational result? Before Stephen Cook (and Leonid Levin), the NP-Complete class was just a theory. No one knew if an NP-Complete problem actually existed. Cook proved that any problem in the NP class (from factoring large numbers to finding graph paths) could be converted (reduced) into a boolean SAT formula in polynomial time.

By providing the very first mathematically proven NP-Complete problem, Cook gave computer scientists a "seed." From that day on, to prove a new problem was NP-Complete, you didn't have to reduce every NP problem to it; you only had to reduce SAT to it!

Standard NP-Complete Problems

Once Cook proved SAT was NP-Complete, Richard Karp published 21 other problems that could be reduced from SAT. According to the syllabus, you must be familiar with these "Standard" NP-Complete problems:

Boolean Satisfiability (SAT / 3-SAT): Can you assign TRUE/FALSE to boolean variables such that the entire formula evaluates to TRUE?
Clique Problem: Does a graph contain a complete subgraph (where every node connects to every other node) of size $k$ ?
Vertex Cover: Can you find a set of $k$ vertices such that every single edge in the graph touches at least one of those vertices?
Hamiltonian Cycle: Is there a path in the graph that visits every vertex exactly once and returns to the start?
Traveling Salesperson (Decision Version): Is there a Hamiltonian cycle with a total weight $\le k$ ?
0/1 Knapsack (Decision Version): Can you pick items such that the total profit is $\ge P$ while the total weight is $\le W$ ?

Polynomial-Time Reduction ( $A \le_p B$ )

(Directly answers 2024 Q8b i & ii)

A Polynomial-Time Reduction is an algorithm that transforms instances of Problem A into instances of Problem B in polynomial time, such that the answer to B is "YES" if and only if the answer to A is "YES".

We write this mathematically as $A \le_p B$ (A reduces to B).

How it proves NP-Completeness: If we already know that Problem A is NP-Complete (e.g., 3-SAT), and we successfully write a polynomial-time reduction from A to our new Problem B (e.g., Vertex Cover), it proves that Problem B is at least as hard as A. If B is also verifiable in polynomial time (in NP), then B is officially proven to be NP-Complete.

Key Properties of Reduction: (Answers 2022 Q1i)

If $A \le_p B$ and $B \in P$ , then $A \in P$ (If B is easy, A must be easy).
If $A \le_p B$ and $A \notin P$ , then $B \notin P$ (If A is hard, B must be hard).
Transitivity: If $A \le_p B$ and $B \le_p C$ , then $A \le_p C$ .

Trace: Reducing 3-SAT to Vertex Cover

1
Step 1
We want to prove that the Vertex Cover problem is NP-Complete. To do this, we will reduce 3-SAT (a known NP-Complete problem) to Vertex Cover. We must convert a boolean formula into an undirected graph.
2
Step 2
Let's take a simple 3-SAT Boolean formula with $n=2$ variables and $m=1$ clauses. Formula: $F = (x_1 \lor \bar{x}_1 \lor x_2)$ . Our goal is to construct a graph $G$ that has a Vertex Cover of size $k$ if and only if $F$ is satisfiable.
3
Step 3
For each variable $x_i$ , we create two vertices in our graph: one for $x_i$ and one for $\bar{x}_i$ . We connect them with an edge. Because they are connected, any valid Vertex Cover MUST select at least one of them. Selecting $x_i$ means we assign the variable TRUE; selecting $\bar{x}_i$ means we assign it FALSE.
4
Step 4
For each clause, we create a triangle of 3 vertices connected to each other. Because it's a triangle, any valid Vertex Cover MUST select at least 2 of the 3 vertices to cover the inner edges.
5
Step 5
We draw edges connecting the literal nodes in the variable gadgets to their corresponding nodes in the clause triangles. To cover these connecting edges, if the Vertex Cover doesn't pick the clause vertex, it must pick the variable vertex (making that literal TRUE, satisfying the clause!).
6
Step 6
We set our target Vertex Cover size to: $k = n + 2m$

$n$ vertices come from selecting exactly one truth value for each of the $n$ variables.

$2m$ vertices come from selecting exactly 2 vertices in each of the $m$ clause triangles. If the graph has a vertex cover of exactly size $k$ , it mathematically proves there is a valid truth assignment satisfying all clauses in $F$ . The reduction is complete!

Knowledge Check

Question 1 of 2

Q1Single choice

What is the primary technique used to prove that a problem is NP-complete?

Divide and conquer

Dynamic programming

Polynomial-time reduction from a known NP-complete problem

Space complexity calculation

NP-Complete and NP-Hard Problems

PYQ Analysis & Exam Preparation — Module 4