40
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ See here for some thoughts on finding suitable partners and ideas for reductions. $\endgroup$ – Raphael Sep 23 '14 at 21:11
18
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Here's an example called the traveling purchaser problem (TPP) that has many hard problems as its special case. $\endgroup$ – Juho Apr 10 '13 at 22:41
  • $\begingroup$ Another example from computability is the special halting problem (which is usually directly proven undecidable), a special case of the general halting problem. $\endgroup$ – Raphael Apr 11 '13 at 7:12
  • $\begingroup$ Is KNAPSACK really a correct reduction from SUBSET-SUM? KNAPSACK asks for value $>=v$ and SUBSET-SUM asks for exact value, no? E.g. a SUBSET-SUM instance $\langle \{5\},4 \rangle$ would be a 'no'-instance (I can't get exactly 4 from only one item with value 5), but your KNAPSACK reduction would reduce that to $\langle \{5\},\{1\},4,1 \rangle$ and $5>4$, so it would be a 'yes'-instance there... Or am I missing something? $\endgroup$ – johnny Dec 18 '17 at 4:07
15
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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:

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


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

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.

$\endgroup$
  • 2
    $\begingroup$ I wonder if you noticed the footnote in the question. I think the answers should be more very specific and showcase how a specific method is applied. This seems pretty vague and general. As an improvement, how about you show how the gadgets can be constructed and used? $\endgroup$ – Juho Apr 10 '13 at 22:35
  • 2
    $\begingroup$ Also: you could explain why something depends on the complexity classes involved, and how so. Also, what if I want to go from $A$ to $B$ or $B$ to $A$, what do I do then? What about the "nearest problem" -- could you give an example of a pair of problems? $\endgroup$ – Juho Apr 10 '13 at 22:38
  • $\begingroup$ the powerpoint shows two examples of gadgets being used. an example of a nearest problem: suppose one has a problem related to number theory. there is a section of G&J related to number theory. etcetera. as for other complexity classes outside of NP, there are many, but the lists of problems are not as thorough or readily obtained. so in other words to narrow the original question maybe it should be limited to NP complete reductions...? $\endgroup$ – vzn Apr 10 '13 at 22:59
  • 2
    $\begingroup$ I recommend adding all the information to the answer, since comments might be deleted any time. The link to the slides might break tomorrow too. What I was getting at with the nearby problem: what do I do exactly once I find a problem that looks similar (assume I'm a total beginner)? $\endgroup$ – Juho Apr 10 '13 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.