MIT 6.1220 — Lecture 14

Intractability (Part II)

Definition (Karp Reduction). A Karp reduction from $Q$ to $\pi$ is a deterministic algorithm $R$ such that:

The algorithm $R$ takes instances $x \in Q$ to instances $y \in \pi$ , such that $Q(x) = \pi(y)$ .
The algorithm $R(x)$ runs in $O(|x|^c)$ for some constant $c$ .

If $R$ exists, we say $Q \leq_P \pi$ . In other words, $Q$ is no harder than $\pi$ .

Claim. Given a Karp reduction from $Q$ to $\pi$ and an efficient $\pi$ -solver, we have an efficient $Q$ -solver.

Proof: Duh, obviously. $\blacksquare$

Note that “Karp” is an abbreviation of “polynomial-time many-one”.

Definition (NP-Hard). A problem $\pi$ is NP-hard if and only if for every $Q \in \textbf{NP}$ , we have $Q \leq_P \pi$ .

Definition (NP-Complete). A problem $\pi$ is NP-complete if and only if $\pi$ is NP-hard and $\pi \in \textbf{NP}$ .

Claim. Consider Circuit-Sat, which asks whether there is a satisfying assignment to a boolean circuit.

We claim that Circuit-Sat is NP-complete.

Proof: It's obvious that Circuit-Sat is in NP.

Now consider any problem $Q \in \textbf{NP}$ . Because $Q$ is in NP, it has a verifier algorithm $A_Q$ . Implement $A_Q$ as a polynomial-sized boolean circuit; that is, express $A_Q$ in hardware. Now run Circuit-Sat on this circuit.

More formally, Turing Machine blah blah blah. $\blacksquare$

Definition (CNF). A formula is in $k$ -CNF (Conjunctive Normal Form) if it is an AND $(\wedge)$ of clauses, each of which is an OR $(\vee)$ of exactly $k$ literals—variables and their negations $(\neg)$ .

Remark. Other definitions exist; for example, some definitions allow $0$ and $1$ to be literals.

For example, $(x_1 \vee \neg x_2) \wedge x_3$ is not in $k$ -CNF for any $k$ , but $(x_1 \vee \neg x_2) \wedge (x_3 \vee x_3)$ is in 2-CNF (but not 3-CNF).

Claim. Consider 3-Sat, which asks whether there is a satisfying assignment for a formula in 3-CNF.

We claim that 3-Sat is NP-complete.

Proof: Obviously it's in NP. Now for any problem $Q \in \textbf{NP}$ , first reduce it to a boolean circuit, and then encode that circuit as a boolean formula.

The point is that 3-CNF is a normal form of all boolean formulas; any boolean formula can be converted into an equisatisfiable 3-CNF formula.

Definition (Vertex Cover). Given a graph, a vertex cover is a set of vertices that contains at least one endpoint from every edge. (Kind of a satisfying assignment to a 2-CNF formula, without negations.)

Remark. To lower-bound the size of a vertex cover by $k$ , find $k$ disjoint edges…

Claim. Consider Vertex-Cover, which asks whether a graph has a vertex cover of size at most $K$ .

We claim that Vertex-Cover is NP-complete.

Proof: Obviously it's in NP. We'll proceed by reducing 3-Sat to Vertex-Cover.

The idea is the following:

Each line segment $a \leftrightarrow b$ requires one vertex from $\{a, b\}$ .
Each triangle $a \leftrightarrow b \leftrightarrow c \leftrightarrow a$ requires two vertices from $\{a, b, c\}$ .

If we have $n$ variables and $m$ clauses, we'll have $n$ line segments and $m$ triangles. (Check: poly-time reduction.)

Now set $K = n + 2m$ . We must then:

Choose exactly one of $\{v_{x_i}, v_{\neg x_i}\}$ for each $i$ .

That is, set each variable $x_i$ to either True or False.
Choose exactly two of $\{v_{C_i, 1}, v_{C_i, 2}, v_{C_i, 3}\}$ for each $i$ .

That is, designate exactly one literal $L$ from each clause $C$ to not shade in… so then, by corollary of the green edges—each joining a clause vertex to the vertex of the literal it names—that literal $L$ must satisfy $C$ .

Formally, a proof goes both ways: 3-Sat $\rightarrow$ Vertex-Cover and Vertex-Cover $\rightarrow$ 3-Sat. Do this! $\blacksquare$

Remark. We should really be speaking in levels of abstraction; there's two gadgets here, the line segment and the triangle. In general, these two gadgets are good starting points.

Claim. Consider Subset-Sum, which, given a set $S$ of positive integers and a target $\ell$ , asks if there is a $T \subseteq S$ with $\sum_{t \in T} t = \ell$ .

We claim that Subset-Sum is NP-complete.

Proof: Obviously it's in NP. We'll proceed by reducing Vertex-Cover to Subset-Sum.

Suppose $G$ has $m$ edges, enumerated $\{e_i\}_{i = 1}^m$ , and we seek a vertex cover of size exactly $K \leq |V|$ ; padding a smaller cover with arbitrary extra vertices makes this the same question as “at most $K$ ”.

For each edge $e_i$ , append $s_{e_{i}} = 4^{i - 1}$ to $S$ .
For each vertex $v$ , append $s_v = 4^m + \sum_{i \in N(v)} 4^{i - 1}$ , where $N(v)$ is the set of indices of edges connected to $v$ .
Set the target sum to $\ell = K \cdot 4^m + 2 \cdot \sum_{i = 1}^m 4^{i - 1}$ .

Of course, we should really be thinking in base $4$ . When we select a subset of $\{s_{e_i}\} \cup \{s_v\}$ ,

The $4^m$ -place of the sum encodes the number of vertices we picked.
The $4^{i - 1}$ -place (for $1 \leq i \leq m$ ) where $e_i = v_1 \leftrightarrow v_2$ encodes how many of $\{e_i, v_1, v_2\}$ were picked.

Let's write out both directions explicitly this time.

Given a vertex cover $V' \subseteq V$ , we pick our subset by choosing:

The vertex-elements $s_v$ for all $v \in V'$ .
The edge-elements $s_e$ for all edges $e = v_1 \leftrightarrow v_2$ with exactly one of $v_1, v_2$ in $V'$ .

Now for the other direction. Given a subset-sum $T \subseteq S$ , just take $V' := \{v \in V \mid s_v \in T\}$ ; the $4^m$ -place forces $|V'| = K$ . Then for each edge $e_i = v_1 \leftrightarrow v_2$ , exactly two of $\{e_i, v_1, v_2\}$ were picked, so at least one of $\{v_1, v_2\}$ is in $V'$ , as desired.

We chose $4$ as the base so that no regrouping can happen. (Think vector-sum, not subset-sum.) $\blacksquare$