Proving NP-Hardness (Gadget Reductions)

Gadget reductions from 3SAT and CLIQUE to show a new problem is hard.

The idea

To prove that a problem $B$ is NP-hard, we reduce a problem already known to be NP-complete to it.

Proposition (Hardness by reduction).

Let $A$ be NP-complete. If there is a polynomial-time computable function $f$ mapping instances of $A$ to instances of $B$ with $x \in A \text{ if and only if } f(x) \in B$ for every $x$, then $B$ is NP-hard.

Choose a known NP-complete source $A$, such as $3SAT$, and construct such an $f$. The direction matters: the reduction goes from the known problem $A$ to the new problem $B$. Any polynomial-time algorithm for $B$ would then decide $A$ as well, so $B$ is at least as hard as $A$. Reducing $B$ to $A$ instead proves nothing, since easy problems also reduce to hard ones.

Both halves of the "if and only if" are necessary. The forward half sends every yes-instance of $A$ to a yes-instance of $B$. The backward half guarantees that no no-instance of $A$ maps to a yes-instance of $B$, so the answer for $f(x)$ genuinely decides $x$.

We build $f$ from gadgets: small fixed pieces of the output, typically one per variable and one per clause of the input, wired so that the structure of $B$ enforces the constraints of $A$. Each gadget encodes a choice, such as a truth value, and the wiring forbids two contradictory choices. The number of gadgets grows linearly with the input, so the construction runs in polynomial time.

The figure shows the construction for the classic reduction from $3SAT$ to $CLIQUE$ on the two-clause formula $(x \lor y \lor z) \land (\overline{x} \lor y \lor w)$: one node per literal, an edge joining two literals exactly when they lie in different clauses and are not contradictory, and a satisfying choice — one literal from each clause — standing out as a clique.

Ways to work on it

Not sure where to start? Take the ten-question placement test.