Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Community wiki. –  Dave Clarke Aug 31 '10 at 13:49
    
@supercooldave: Thanks - I suppose I should have done that while posting. My oversight! –  Neeldhara Aug 31 '10 at 13:53
    
@Jukka: Thanks! I thought that's what supercooldave's edit did. I now realize that edit added a tag. It's now a CW :) –  Neeldhara Aug 31 '10 at 14:06
8  
Perhaps the poster should clarify what is meant by "from the book." I would have thought that (in analogy with proofs from the book) algorithms from the book are all short, simple to state, elegant and work almost magically. However, the other thread has many posts with insanely complex algorithms that don't satisfy any of the properties I mentioned. –  Robin Kothari Aug 31 '10 at 14:26
3  
@Robin: Perceptions differ. I didn’t find any of the proofs from “Proofs from THE BOOK” simple (well, almost none). And already the second proof (Bertrand’s postulate) requires several pages, so they’re not short either. – Conversely, I find many of the algorithms in the related thread quite simple (in hindsight, obviously), and there’s no denying that they are short. –  Konrad Rudolph Sep 8 '10 at 11:21

9 Answers 9

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.

share|improve this answer
    
An explanation of this reduction (if I am not mistaken) can be found on page 7 of "Provable Security of Cryptosystems: A Survey". Here is a link: cs.yale.edu/publications/techreports/tr288.pdf –  Neeldhara Sep 1 '10 at 5:23

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.

share|improve this answer
2  
Thank you! This appears most promising, and also entirely new to me. I should be spending some time on that tutorial and the other references too. –  Neeldhara Sep 1 '10 at 16:35

Integer multiplication to fast Fourier transforms!

share|improve this answer
6  
and the corollary: string matching to FFTs ! –  Suresh Venkat Sep 3 '10 at 6:16

Cook-Levin Theorem

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

share|improve this answer

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.

share|improve this answer
1  
Rice-Shapiro's generalization is even more beautiful. See Cutland's exposition: books.google.com/…) –  Diego de Estrada Sep 2 '10 at 1:51

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.

share|improve this answer

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.

share|improve this answer
1  
The reduction using NAESAT instead of 3SAT (in Papadimitriou's book) is more direct. –  Diego de Estrada Sep 2 '10 at 2:21

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

reducing sorting to a convex hull problem.

share|improve this answer

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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