TCS: NP Completeness

NP Completeness

Polynomial-Time Reductions

The direction records which solver would help: $A\le_p B$ means a solver for $B$ can solve $A$. To prove a new problem hard, reduce a known hard problem to it

Reductions compose. Consequently, a polynomial-time algorithm for one NP-complete language implies $\mathrm P=\mathrm{NP}$

For each construction, check four things: the output instance, its polynomial construction cost, the forward implication, and the reverse implication

Cook-Levin Theorem

SAT has a polynomial-time verifier, so the main task is to encode an arbitrary NP computation as a formula

Let $V(x,y)$ be a polynomial-time verifier running for at most $T=\operatorname{poly}(|x|)$ steps. Pad its accepting computations so that they remain accepting through step $T$

Computation Tableaux

A configuration records the tape contents, the head location, and the state. During $T$ steps, at most polynomially many tape cells are relevant

Introduce Boolean variables for every cell at every time. Use a finite alphabet that records a machine state together with the scanned tape symbol at the head position

The formula enforces three kinds of conditions

$$\Phi_x=Phi_{\mathrm{start}}\land \Phi_{\mathrm{move}}\land \Phi_{\mathrm{accept}}$$

• $\Phi_{\mathrm{start}}$ fixes the input portion to $x$, leaves the certificate portion free, and specifies a valid initial configuration
• $\Phi_{\mathrm{move}}$ requires every neighboring pair of rows to follow the transition rules
• $\Phi_{\mathrm{accept}}$ requires an accepting final configuration

For a fixed machine, whether a cell in the next row is legal depends on a constant-size neighborhood in the previous row. Each local consistency condition therefore has a constant-size Boolean representation

There are polynomially many rows and columns, so the complete formula is polynomial in $|x|$. An accepting certificate yields a satisfying tableau, while a satisfying tableau encodes an accepting computation

$$x\in L\quad\Longleftrightarrow\quad\Phi_x\in\operatorname{SAT}$$

From SAT to 3-SAT

Introduce a variable for the output of each gate of a Boolean circuit computing the formula. For an AND gate $z=a\land b$, its behavior is enforced by

$$(\neg z\lor a)\land(\neg z\lor b) \land(z\lor\neg a\lor\neg b)$$

An analogous constant-size encoding handles NOT and OR gates. Add a unit clause requiring the output variable to be true

The resulting 3-CNF is satisfiable exactly when the original formula is satisfiable. It is an equisatisfiable encoding with auxiliary variables, rather than an equivalent formula over only the original variables

Vertex Cover, Independent Set and Clique

3-SAT to Vertex Cover

For a formula with $n$ variables and $m$ clauses of three literal occurrences, construct a graph as follows

1. For each variable, add vertices $x_i,\neg x_i$ connected by an edge
2. For each clause, add a triangle with one vertex for each literal occurrence
3. Connect each clause vertex to the variable vertex carrying the same literal
4. Set the cover budget to $n+2m$

Every variable edge needs at least one chosen endpoint, and every clause triangle needs at least two. Thus a cover within the budget must spend exactly these amounts

Given a satisfying assignment, choose the true literal vertex from each variable edge. In each clause triangle, leave one true literal occurrence unchosen and choose the other two. Its connecting edge is covered at the true variable vertex, so all edges are covered

Conversely, a cover of size $n+2m$ chooses exactly one variable vertex per pair and leaves exactly one clause vertex unchosen. The connecting edge from that unchosen vertex forces its corresponding variable vertex to be chosen. Reading chosen variable vertices as true therefore satisfies every clause

Two Simple Transformations

For a graph $G=(V,E)$,

$$C\text{ is a vertex cover} \quad\Longleftrightarrow\quad V\setminus C\text{ is an independent set}$$

An independent set in $G$ is a clique in the complement graph $\overline G$. Hence

$$(G,k)\in\operatorname{VC} \iff(G,|V|-k)\in\operatorname{INDSET} \iff(\overline G,|V|-k)\in\operatorname{CLIQUE}$$

All three problems have efficiently checkable witnesses, completing their NP-completeness proofs

Not-All-Equal SAT and 3-Coloring

A not-all-equal constraint $\operatorname{NAE}(a,b,c)$ accepts exactly the Boolean triples containing both a true and a false value

One route from 3-SAT introduces a shared variable $z$ and replaces each clause $(a\lor b\lor c)$ by $\operatorname{NAE}(a,b,c,z)$. Complementing all variable values preserves every NAE constraint, so any satisfying assignment can be oriented to have $z=0$

Four-input constraints can be split using a fresh variable $u$

$$\operatorname{NAE}(a,b,c,d) \iff\exists u:\operatorname{NAE}(a,b,u) \land\operatorname{NAE}(\neg u,c,d)$$

When $a=b$, the first constraint forces $u=\neg a$, and the second excludes precisely the case $a=b=c=d$. When $a\ne b$, the first constraint permits either value of $u$, allowing the second to be satisfied

A Clause Gadget for 3-Coloring

Create a reference triangle with colors named $T,F,B$. For each variable, connect its two literal vertices to each other and connect both to the reference vertex $B$. They must receive opposite colors $T,F$

For each NAE clause, add a fresh triangle $a_1,a_2,a_3$ and connect $a_i$ to the corresponding literal vertex $\ell_i$

If all three literals have the same color, the clause triangle has only two available colors and cannot be colored. If the literals contain both $T$ and $F$, assign $T$ to a triangle vertex attached to an $F$ literal, $F$ to one attached to a $T$ literal, and $B$ to the remaining vertex

Thus the clause triangle is extendibly 3-colorable exactly when the NAE constraint holds. This is a polynomial reduction to 3-COLORING

Hamiltonian Cycles

Hamiltonian cycle has a polynomial certificate: a cyclic ordering of all vertices. Its NP-hardness can be shown by a gadget reduction from vertex cover

The construction replaces each original edge by a gadget whose complete traversals correspond to selecting its left endpoint, its right endpoint, or both. There is no valid traversal representing selection of neither endpoint

Gadget interfaces associated with the same original vertex are linked into a chain. Selector vertices limit the number of such chains used. A small vertex cover supplies a Hamiltonian traversal, while a Hamiltonian cycle must account for every edge gadget and therefore induces a cover

The exact gadget and its allowed traversals are part of the construction; checking only that the graph has polynomial size does not prove the reverse implication. The lecture’s Hamiltonian-cycle section contains the gadget diagram

Hamiltonian path and cycle are closely related. Adding one new vertex adjacent to every original vertex transforms an undirected Hamiltonian-path instance into a Hamiltonian-cycle instance: remove the new vertex from a cycle to recover the path

In the other direction, split a chosen cycle vertex into two copies with its original neighbors and attach a fresh leaf to each copy. A Hamiltonian path must run between the leaves, and identifying the split copies recovers a Hamiltonian cycle

MAX-CUT from NAE-3-SAT

A triangle contributes two cut edges exactly when its three vertices are not all on the same side

Construct a weighted multigraph with a vertex for each literal. Give each pair $x_i,\neg x_i$ an edge of positive integer weight $W$, and add the three unit-weight edges of a triangle for each clause, retaining multiplicities

The sum of the separate upper bounds is

$$K=nW+2m$$

A satisfying NAE assignment reaches $K$ by separating opposite literals and cutting each clause triangle twice. Conversely, reaching $K$ requires every variable edge and every triangle to attain its individual upper bound, giving a consistent NAE assignment

To obtain a simple unweighted graph, replace each unit of edge weight by a three-edge path with fresh internal vertices. Such a path contributes at most three cut edges when its endpoints differ and at most two when they agree; both bounds are achievable independently

If the total edge weight is $q$, this transforms the cut threshold $K$ into $2q+K$. The construction stays polynomial for polynomially bounded weights, so the usual unweighted MAX-CUT decision problem is NP-complete as well

NP-Intermediate Languages

The idea is delayed diagonalization. Pad SAT instances by an amount that grows carefully: enough to obstruct every proposed polynomial reduction making the padded language complete, but slowly enough to defeat every proposed polynomial-time decider

The padding schedule is part of the effective construction. Arbitrarily choosing a large padding function does not automatically prove either property

The theorem establishes the existence of intermediate languages under $\mathrm P\ne\mathrm{NP}$. It does not classify a particular natural problem such as graph isomorphism