NP-Hardness Part 2 (NP-Hard, NP-Complete, SAT, Cook-Levin, Reductions)

Lecture slides (PDF)

NP-Hard

Definition (NP-Hard). A problem $X$ is NP-hard if every problem in $\mathbf{NP}$ polynomial-time reduces to $X$:

\[\forall\, A \in \mathbf{NP}, \quad A \le_p X.\]

Informally, $X$ is at least as hard as every problem in NP. NP-hard problems need not be decision problems, and they need not belong to NP themselves. They may be strictly harder. If $X$ is NP-hard and admits a polynomial-time algorithm, then every problem in $\mathbf{NP}$ could be solved in polynomial time, implying $\mathbf{P} = \mathbf{NP}$, which is widely conjectured to be false.

NP-Complete

Definition (NP-Complete). A problem $X$ is NP-complete if:

  1. $X \in \mathbf{NP}$: yes-instances of $X$ have a certificate verifiable in polynomial time, and
  2. $X$ is NP-hard: every problem in $\mathbf{NP}$ reduces to $X$ in polynomial time.

NP-complete problems are simultaneously the hardest problems inside NP. If any one of them is in $\mathbf{P}$, then $\mathbf{P} = \mathbf{NP}$.

The diagram below shows how the complexity classes relate (assuming $\mathbf{P} \ne \mathbf{NP}$):

Satisfiability (SAT and 3-SAT)

Terminology. A literal is a variable $x_i$ or its negation $\neg x_i$. A clause is a disjunction (OR) of literals: $(\ell_1 \lor \ell_2 \lor \cdots \lor \ell_m)$. A formula is in conjunctive normal form (CNF) if it is a conjunction (AND) of clauses.

Satisfiability (SAT). Given a Boolean formula $\phi$ in CNF, does there exist a truth assignment to the variables that makes $\phi$ evaluate to true (i.e., satisfies every clause)?

Example. $\phi = (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2 \lor x_3)$. Setting $x_1 = \mathrm{T},\, x_2 = \mathrm{T},\, x_3 = \mathrm{F}$ makes both clauses true, so $\phi$ is satisfiable.

SAT is in NP: a satisfying assignment is the certificate, and verification takes $O(n)$ time (substitute the assignment into each clause and check).

3-SAT. The restriction of SAT where every clause contains exactly 3 literals. For example:

\[\phi = (x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (x_1 \lor \neg x_2 \lor x_3).\]

3-SAT is also in NP for the same reason as SAT.

Cook-Levin Theorem

Theorem (Cook 1971; Levin 1973). SAT is NP-complete. In particular, 3-SAT is NP-complete.

The proof shows that any NP problem (described by a polynomial-time verifier) can be encoded as a SAT instance in polynomial time, using the computation of the verifier as a circuit. We omit the proof here.

The significance is that SAT (and 3-SAT) serves as the starting point for a chain of reductions: once we know 3-SAT is NP-complete, we can prove other problems NP-complete by reducing from 3-SAT (or from any known NP-complete problem).

Proving NP-Completeness

To prove a new problem $B$ is NP-complete:

  1. Show $B \in \mathbf{NP}$: Exhibit a certificate for yes-instances and a polynomial-time verification algorithm.
  2. Show $B$ is NP-hard: Choose a known NP-complete problem $A$ (e.g., 3-SAT) and construct a polynomial-time reduction $A \le_p B$.

Since every NP problem reduces to $A$ by NP-hardness of $A$, and $A$ reduces to $B$, transitivity gives that every NP problem reduces to $B$. Combined with step 1, $B$ is NP-complete.

Reduction: 3-SAT reduces to Independent Set

Recall. An independent set in a graph $G = (V, E)$ is a set $S \subseteq V$ such that no two vertices in $S$ are adjacent. The Independent Set decision problem asks: given $G$ and an integer $k$, does $G$ contain an independent set of size $\ge k$?

Theorem. Independent Set is NP-complete.

Proof.

Step 1: Independent Set is in NP. Given a set $S$ as the certificate, verify that $\lvert S \rvert \ge k$ and that no edge has both endpoints in $S$. This takes $O(V + E)$ time.

Step 2: 3-SAT $\le_p$ Independent Set. We describe a polynomial-time reduction.

Construction. Given a 3-CNF formula $\phi$ with clauses $C_1, \ldots, C_k$ over variables $x_1, \ldots, x_n$, build a graph $G$ and integer $k$ as follows:

The construction runs in polynomial time: $3k$ vertices and at most $\binom{3k}{2}$ edges.

Example. Let $\phi = (x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (x_1 \lor \neg x_2 \lor x_3)$ with $k = 3$. The graph $G$ has three triangles (one per clause) and six conflict edges (dashed) connecting complementary literals across triangles. The assignment $x_1 = x_2 = x_3 = \mathrm{T}$ satisfies all three clauses; picking one true literal per clause gives the independent set ${x_1,\, x_2,\, x_3}$ highlighted in yellow.

Correctness: We prove $\phi$ is satisfiable $\iff$ $G$ has an independent set of size $k$.

$(\Rightarrow)$ Suppose $\phi$ has a satisfying assignment $\sigma$. For each clause $C_i$, at least one literal $\ell_{i,a}$ is true under $\sigma$; add vertex $v_{i,a}$ to set $S$.

So $S$ is an independent set of size $k$.

$(\Leftarrow)$ Suppose $G$ has an independent set $S$ with $\lvert S \rvert = k$. Each triangle is a clique of size 3, so $S$ contains at most one vertex per triangle. Since $\lvert S \rvert = k$ and there are $k$ triangles, $S$ has exactly one vertex per triangle. Define an assignment $\sigma$ by setting each literal in $S$ to true. This is well-defined: if $S$ contained $v_{i,a}$ labeled $x_r$ and $v_{j,b}$ labeled $\neg x_r$, the conflict edge between them would contradict $S$ being independent. For variables unconstrained by $S$, set them arbitrarily. Every clause $C_i$ is satisfied because the vertex chosen from triangle $i$ corresponds to a true literal in $C_i$. $\square$

Reduction: 3-SAT reduces to ILP

An integer linear program (ILP) is a system of linear inequalities with integer-valued variables. The ILP Feasibility decision problem asks: given coefficients $c_{ji}$ and right-hand sides $d_j$, does there exist integers $y_1, \ldots, y_n$ satisfying

\[\sum_{i=1}^{n} c_{ji}\, y_i \;\ge\; d_j \quad \text{for all } j?\]

Theorem. ILP Feasibility is NP-complete.

Proof.

Step 1: ILP is in NP. A certificate is an integer assignment $y \in \mathbb{Z}^n$. Checking each constraint takes $O(n)$ time, so verification is polynomial.

Step 2: 3-SAT $\le_p$ ILP. We describe a polynomial-time reduction.

Construction. Given a 3-CNF formula $\phi$ with clauses $C_1, \ldots, C_m$ over variables $x_1, \ldots, x_n$:

\[\sum_{i \in P_j} y_i \;+\; \sum_{i \in N_j} (1 - y_i) \;\ge\; 1.\]

The ILP has $n$ variables, $m + 2n$ constraints, all constructible in polynomial time.

Example (satisfiable). For $\phi = (x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (x_1 \lor \neg x_2 \lor x_3)$:

\[\begin{aligned} y_1 + y_2 + (1-y_3) &\;\ge\; 1 & (C_1{:}\ P=\{1,2\},\ N=\{3\})\\ (1-y_1) + y_2 + y_3 &\;\ge\; 1 & (C_2{:}\ P=\{2,3\},\ N=\{1\})\\ y_1 + (1-y_2) + y_3 &\;\ge\; 1 & (C_3{:}\ P=\{1,3\},\ N=\{2\})\\ 0 \le y_i \le 1,\quad y_i &\;\in\; \mathbb{Z}, & i = 1,2,3. \end{aligned}\]

The assignment $y_1 = y_2 = y_3 = 1$ satisfies all three constraints: $1+1+0 = 2 \ge 1$, $0+1+1 = 2 \ge 1$, $1+0+1 = 2 \ge 1$.

Example (unsatisfiable). For $\phi = (x_1 \lor x_1 \lor x_1) \land (\neg x_1 \lor \neg x_1 \lor \neg x_1)$, the ILP becomes:

\[\begin{aligned} 3y_1 &\;\ge\; 1 & (C_1)\\ 3(1-y_1) &\;\ge\; 1 & (C_2)\\ 0 \le y_1 \le 1,\quad y_1 &\;\in\; \mathbb{Z}. \end{aligned}\]

$C_1$ requires $y_1 \ge \tfrac{1}{3}$, so $y_1 = 1$. $C_2$ requires $y_1 \le \tfrac{2}{3}$, so $y_1 = 0$. The two constraints are contradictory — the ILP is infeasible, confirming $\phi$ is unsatisfiable.

Correctness: We prove $\phi$ is satisfiable $\iff$ the ILP has a feasible solution.

$(\Rightarrow)$ Let $\sigma$ be a satisfying assignment. Set $y_i = 1$ if $\sigma(x_i) = \mathrm{T}$, else $y_i = 0$. Each clause $C_j$ has at least one true literal: a true positive literal $x_i$ contributes $+1$ via $y_i = 1$, and a true negative literal $\neg x_i$ contributes $+1$ via $(1 - y_i) = 1$. So $\sum_{i \in P_j} y_i + \sum_{i \in N_j}(1 - y_i) \ge 1$ holds for every $j$.

$(\Leftarrow)$ Let $y \in \mathbb{Z}^n$ with $0 \le y_i \le 1$ be a feasible ILP solution. Set $\sigma(x_i) = \mathrm{T}$ iff $y_i = 1$. For each clause $C_j$, the constraint gives $\sum_{i \in P_j} y_i + \sum_{i \in N_j}(1 - y_i) \ge 1$, so at least one literal in $C_j$ is true under $\sigma$. $\square$