NP-Hard and NP-Complete

Alternative View: Nondeterministic Programming

Consider extending C++ with the following construct:

either {
    // statements 1
} or {
    // statements 2
}

When this executes, two parallel universes are created. If any one returns yes, the program outputs yes; otherwise no. Running time is the time of the longest-running universe.

NP = the set of problems solvable in polynomial time using this nondeterministic C++.

(NP stands for Nondeterministic Polynomial; this definition is equivalent to the certifier-based one.)

NP-Hard and NP-Complete Definitions

Definition 1. Problem $X$ is NP-hard if every $Y \in \text{NP}$ satisfies $Y \leq_P X$.

Definition 2. Problem $X$ is NP-complete if $X \in \text{NP}$ and $X$ is NP-hard.

NP-complete problems are the “hardest” problems within NP.

Theorem 1. If $X$ is NP-complete, then $X$ can be solved in polynomial time if and only if $\text{P} = \text{NP}$.

Proof.

If $\text{P} = \text{NP}$: $X \in \text{NP} = \text{P}$, so a polynomial-time algorithm exists.
If $X$ is solvable in polynomial time: for any $Y \in \text{NP}$, $Y \leq_P X$, so $Y$ is also solvable in polynomial time. ∎

Cook-Levin Theorem

Theorem 2 (Cook-Levin). 3-SAT is NP-complete.

This is the first NP-completeness proof and is the starting point for all subsequent ones.

Recipe for proving NP-completeness of a new problem $X$:

Show $X \in \text{NP}$. (Construct an efficient certifier)
Show $Y \leq_P X$ for some already-known NP-complete problem $Y$.

3-Dimensional Matching is NP-Complete

Problem Definition

Problem 3 (3-Dimensional Matching). Given three disjoint sets $X, Y, Z$ of equal size ($\lvert X\rvert=\lvert Y\rvert=\lvert Z\rvert=n$) and $T \subseteq X \times Y \times Z$: does $T$ contain $n$ triples that together include each element of $X \cup Y \cup Z$ exactly once?

Theorem 3. 3-Dimensional Matching is NP-complete.

Part 1: $\in$ NP

For a yes-instance, present as hint a subset $T’ \subseteq T$ with $\lvert T’\rvert=n$. We verify in polynomial time that $\lvert T’\rvert=n$, $T’ \subseteq T$, and each element of $X \cup Y \cup Z$ appears exactly once.

Part 2: 3-SAT $\leq_P$ 3-Dimensional Matching

From a 3-SAT instance with $n$ variables and $k$ clauses, construct three gadgets.

Variable Gadget

For each variable $x_i$:

$A_i := \lbrace a_{i,1}, \ldots, a_{i,2k}\rbrace$, $B_i := \lbrace b_{i,1}, \ldots, b_{i,2k}\rbrace$
Variable triples $t_{i,\ell} = (a_{i,\ell},\ a_{i,\ell+1},\ b_{i,\ell})$ for $\ell = 1, \ldots, 2k$ (with $a_{i,2k+1} := a_{i,1}$)

These are the only triples containing elements of $A_i$.

Interpretation: If $x_i$ is true, select triples with odd $\ell$ → $b_{i,j}$ covered for odd $j$. If false, select even.

Clause Gadget

For each clause $C_j$, define $P_j := \lbrace p_j, p’_j\rbrace$ and add three clause triples:

If $C_j$ contains $x_i$: add $(p_j, p’j, b{i,2j})$
If $C_j$ contains $\bar{x}i$: add $(p_j, p’_j, b{i,2j-1})$

The only triples containing $p_j$ or $p’_j$ are these three.

Cleanup Gadget

$(n-1)k$ cleanup gadgets: for $m = 1, \ldots, (n-1)k$, define $Q_m := \lbrace q_m, q’m\rbrace$ and add cleanup triples $(q_m, q’_m, b{i,\ell})$ for all $i, \ell$.

Set Partition

$X := \{a_{i,j}\ \mid\ j \text{ even}\} \cup \{p_j\} \cup \{q_m\}$ $Y := \{a_{i,j}\ \mid\ j \text{ odd}\} \cup \{p'_j\} \cup \{q'_m\}$ $Z := \{b_{i,j}\ \mid\ 1 \leq i \leq n,\ 1 \leq j \leq 2k\}$

$\lvert X\rvert = \lvert Y\rvert = \lvert Z\rvert = 2nk$, $\lvert T\rvert = O(n^2k^2)$ — the construction is completed in polynomial time.

Equivalence

3-SAT yes $\Rightarrow$ 3DM yes:

Fix a satisfying assignment. If $x_i$ is true, select variable triples with odd $\ell$; if false, even.
For each clause $C_j$, select the clause triple corresponding to a true literal (the corresponding $b_{i,\ell}$ is not yet covered).
Cover remaining $B_i$ elements and $\cup_m Q_m$ using cleanup triples.

3DM yes $\Rightarrow$ 3-SAT yes:

Elements of $A_i$ can only be covered by variable triples → the matching selects either all odd or all even $\ell$ triples.
Assign $x_i$ = true if odd triples selected, false if even.
For each clause $C_j$, the selected clause triple’s $b_{i,\ell}$ reveals the corresponding variable is true → the clause is satisfied. ∎