What are common techniques for reducing problems to each other?

Question

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as some other problem $L_2$ by mapping instances from $L_2$ to solution-equivalent ones in $L_1$. Essentially, we show that any solver for $L_1$ can also solve $L_2$ if we allow it to use the reduction function as preprocessor.

I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?

What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?

^{This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!}

Answer 1

The Special Case

Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case.

In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.

Simple Example

Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.

Simple exercise problem

Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.

3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.

Example

Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.

We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate

$\qquad \displaystyle f(A) = \begin{cases} \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\ \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else} \end{cases}$

where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.

Exercise Problem

Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

Show that LONGEST-PATH is NP-hard.

HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
Note in particular how reducing from HAMILTON-PATH requires more work.

Answer 2

Leveraging a known nearby problem

When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem.

Example problem

Consider a problem

$$\text{DOUBLE-SAT} = \{ \varphi \mid \varphi \text{ is a boolean formula with at least 2 satisfying assignments } \}$$

we wish to show is $\mathsf{NP}$-complete. We quickly note that it is very close to a problem we already know is hard, namely the satisfiability problem (SAT).

The membership to $\mathsf{NP}$ is straightforward to show. The certificate is two assignments. Clearly, it can be checked in polynomial time whether the assignments satisfy a formula.

$\mathsf{NP}$-hardness follows from a reduction from $\text{SAT}$. Given a formula $\varphi$, we modify it by introducing a new variable $v$. We add a new clause $(v \vee \neg v)$ to the formula. Now, if $\varphi$ is satisfiable, it will be satisfiable with both $v = \perp$ and $v = \top$. Hence, $\varphi$ has at least 2 satisfying assignments. On the other hand, if $\varphi$ is not satisfiable, it will definitely not become satisfiable regardless of the value of $v$.

It follows that $\text{DOUBLE-SAT}$ is $\mathsf{NP}$-complete, which is what we wanted to show.

Finding nearby problems

Reducing problems is kind of an art, and experience and ingenuity are often needed. Fortunately, many hard problems are already known. Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness is a classic one with its appendix listing many problems. Google Scholar is also a friend.

Answer 3

In computability, we often investigate sets of Turing machines. That is, our objects are functions and we have access to a Gödel numbering. That's great because we can do pretty much what we want with the input function, as long as we remain computable.

Assume we want to show that $L$ is not decidable. Our goal is to get to the equivalence of doom

$\qquad \langle M \rangle \in K \iff \langle f_M \rangle \in L$

with $K = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ halts} \}$ the halting problem (or any other undecidable language/problem).

Thus, we need to come up with a computable¹ mapping $\langle M \rangle \mapsto \langle f_M \rangle$ so that $f_M$ is always computable. This is a creative act informed by the equivalence of doom. See some examples to get an idea of how this works:

• Mapping Reductions to Complement of $A_{\mathrm{TM}}$
• Is it possible to mapping reduce either of these languages to the other?

The same works for showing that $L$ is not semi-decidable by choosing non-semi-decidable languages as reduction partner, e.g. $\overline{K}$:

• Is regularity of the language accepted by a given Turing machine a semi-decidable property?
• Is the set of computable constant functions recursively enumerable?

---

1. This is where the Gödel numbering comes in: we get computability of this mapping (usually) for free.

Answer 4

it depends on the complexity classes involved, and whether one wants to reduce from a given $A$ to an unknown $B$, or an unknown $B$ to a given $A$. the common scenario is to prove problems NP Hard or NP Complete. a common technique is to construct "gadgets" in one domain that behave in a certain way, mimicking the behavior of another domain. for example to convert SAT to vertex cover, one constructs "gadgets" in vertex cover that behave similarly to clauses of SAT, eg in the following slide show: NP Complete reductions by Krishnamoorthy (also with an example for Hamilton path).

a useful strategy is to work from large compilations of problems from the complexity class in question and find the "apparent nearest problems" to the problem being studied. an excellent reference along these lines is Computers and Intractability, a guide to the theory of NP completeness, Garey and Johnson organized by different problem types.