Reductions from the book.

Question

This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about algorithms from the book. Hence a separate query!

Reductions of all kinds are most welcome.

I'll start off with the really simple reduction from vertex cover to multicut on stars. The reduction almost suggests itself once the source problem is identified (before which I would find it hard to believe that the problem would be hard on stars). This reduction involves constructing a star with $n$ leaves, and associating a pair of terminals with every edge in the graph, and it is "easy to see" that it works. I will update this with a link to a reference, once I find one.

Those who are missing the context of the book may want to look at the question about Algorithms from the book.

Update: I realize that I was not entirely clear as to what qualifies as a reduction from the book. I find this issue a little bit tricky, so I confess to half-deliberately dodging the issue by slipping in a reference to the other thread :)

So let me describe what I had in mind, and I suppose it goes without saying - YMMV in this regard. I intend a direct analogy to the original intent of Proofs from the Book. I have seen reductions that are awfully clever, and leave me gaping at how that sequence of thoughts might have occurred to anyone. While such reductions leave me with a definite sense of awe, those are not the examples that I am looking to collect in this context.

What I am looking for are reductions that are described without too much difficulty, and are perhaps mildly surprising, for the reason that they are easy to grasp but aren't easy to come up with. If you estimate that the reduction in question will require a lecture to cover, then likely it doesn't fit the bill, although I am sure there might be exceptions where the high-level idea is elegant and the devil's in the details (for the record, I'm not sure I can think of any).

The example I gave was deliberately simple, and hopefully somewhat - if not perfectly - illustrative of these characteristics. The first time I heard about multi-cut was in a classroom, and our instructor began by saying that not only is it NP-hard in general, it is NP-hard even when restricted to trees... {dramatic pause} of height one. I recall not being able to prove it immediately, although it seems obvious in retrospect.

I suppose obvious in retrospect closely describes what I am looking for. I am not sure if this has anything to do with the complexity of the description - perhaps there are situations where something apparently murky might classify as elegant - feel free to bring up your examples (exceptions?), but I would really appreciate a justification. Given that after some point this is a matter of taste, you should certainly feel free to find what I see as insanely complex, perfectly beautiful. I am looking forward to seeing a variety of examples!

Answer 1

Rabin shows the one-wayness of (x^2 mod N=pq) without the factorization of N by a reduction showing that if you can take square roots module N=pq then you can factor N.

Answer 2

In machine learning, there are lots of interesting reductions. Here are some examples:

• multiclass classification to binary classification (link) -- one can solve a problem of choosing among many classes by solving easier problems of choosing between two.
• strong learning to weak learning (boosting) -- one can achieve arbitrarily low error rates given the ability to achieve slightly better than random.
• ranking to classification (link)
• squared loss to classification (probing) -- one can estimate class membership probabilities by using a classifier with a small error rate.

A tutorial by Alina Beygelzimer, John Langford, and Bianca Zadrozny covers some others.

Answer 3

Cook-Levin Theorem

Any problem in NP can be reduced in polytime by a deterministic turing machine to SAT. For reference see 1.

Answer 4

Integer multiplication to fast Fourier transforms!

Answer 5

Rice's theorem

One of my favorites. It reduces the halting problem to any index set (or it's complement). See, for instance, Sipser, problem 5.28.

Answer 6

SAT to 3SAT

Starting from the basics. The cases where the number of literals $k$ is smaller or equal to 3 are trivially reduced to 3SAT. When $k \gt 3$, it's possible to add a polynomial number of extra variables in such a way that the truth assignment is kept and clauses are split to have exactly 3 literals. For reference see 1.

Answer 7

3SAT to 3COL

Using gadgets to reduce 3SAT to the problem of deciding if a graph is colorable with 3 colors. For reference see 1.

Answer 8

In the sense of saying - oh that was simple - in retrospect:

reducing sorting to a convex hull problem.

Answer 9

EXACT COVER BY 3-SETS to SUBSET SUM

EXACT COVER BY 3-SETS: given $U=\{1,2,\ldots,3m\}$ and $S_1,\ldots,S_n$ 3-subsets of $U$, are there $m$ disjoint sets that cover $U$?

SUBSET SUM: given integers $w_1,\ldots,w_n$ and $K$, is there a subset of the given integers that adds up to exactly $K$?

Think of the sets $S_i$ as vectors in $\{0,1\}^{3m}$, and think of this vectors as integers in base $n+1$, so that $S_i$ becomes $w_i=\sum_{j\in S_i} (n+1)^{3m-j}$. Set $K=\sum_{j=0}^{3m-1} (n+1)^j$.

(My source was Papadimitriou's book.)