<p>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.</p>

CC BY-SA 2.5
2010-09-01T05:23:34.417Z
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: http://www.cs.yale.edu/publications/techreports/tr288.pdf
Neeldhara
CC BY-SA 2.5
2010-08-31T20:49:17.977Z
2010-08-31T20:49:17.977Z
Noam
<p>In machine learning, there are lots of interesting reductions. Here are some examples:</p>

<ul>
<li><strong>multiclass classification to binary classification</strong> (<a href="http://jmlr.csail.mit.edu/papers/volume1/allwein00a/allwein00a.pdf">link</a>) -- one can solve a problem of choosing among many classes by solving easier problems of choosing between two.</li>
<li><strong>strong learning to weak learning</strong> (<a href="http://en.wikipedia.org/wiki/AdaBoost">boosting</a>) -- one can achieve arbitrarily low error rates given the ability to achieve slightly better than random.</li>
<li><strong>ranking to classification</strong> (<a href="http://hunch.net/~jl/projects/reductions/ranking/journal_final/ranking.pdf">link</a>)</li>
<li><strong>squared loss to classification</strong> (<a href="http://hunch.net/~jl/projects/reductions/probing/aistat_real_final/aistat_final.pdf">probing</a>) -- one can estimate class membership probabilities by using a classifier with a small error rate.</li>
</ul>

<p>A <a href="http://hunch.net/~reductions_tutorial/">tutorial</a> by Alina Beygelzimer, John Langford, and Bianca Zadrozny covers some others.</p>

CC BY-SA 2.5
2010-09-01T16:35:21.757Z
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
CC BY-SA 2.5
2010-09-01T15:57:28.360Z
2010-09-01T15:57:28.360Z
Lev Reyzin
<p><strong>Cook-Levin Theorem</strong></p>

<p>Any problem in NP can be reduced in polytime by a deterministic turing machine to SAT. For reference see <a href="http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem">1</a>.</p>

CC BY-SA 2.5
2010-08-31T14:58:19.057Z
2010-08-31T14:58:19.057Z
Rui Ferreira
<p>Integer multiplication to fast Fourier transforms!</p>

CC BY-SA 2.5
2010-09-03T06:16:23.587Z
and the corollary: string matching to FFTs !
Suresh Venkat
CC BY-SA 2.5
2010-09-03T03:44:25.203Z
2010-09-03T03:44:25.203Z
Jeffε
<p><strong>Rice's theorem</strong></p>

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

CC BY-SA 2.5
2010-09-02T01:51:07.473Z
Rice-Shapiro's generalization is even more beautiful. See Cutland's exposition: http://books.google.com/books?id=wAstOUE36kcC&lpg=PA130&ots=juxGhcu1Xm&pg=PA130#v=onepage&q&f=false)
didest
CC BY-SA 2.5
2010-08-31T15:51:12.680Z
2010-08-31T15:51:12.680Z
Michaël Cadilhac
<p><strong>SAT to 3SAT</strong></p>

<p>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 <a href="http://www.soe.ucsc.edu/classes/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf" rel="nofollow">1</a>. </p>

CC BY-SA 2.5
2010-08-31T14:33:52.857Z
2010-08-31T14:33:52.857Z
Rui Ferreira
<p><strong>3SAT to 3COL</strong></p>

<p>Using gadgets to reduce 3SAT to the problem of deciding if a graph is colorable with 3 colors. For reference see <a href="http://www.shannarasite.org/kb/kbse60.html" rel="nofollow">1</a>.</p>

CC BY-SA 2.5
2010-09-02T02:21:17.137Z
The reduction using NAESAT instead of 3SAT (in Papadimitriou's book) is more direct.
didest
CC BY-SA 2.5
2010-08-31T14:46:42.667Z
2010-08-31T14:46:42.667Z
Rui Ferreira
<p><strong>EXACT COVER BY 3-SETS to SUBSET SUM</strong></p>

<p>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$?</p>

<p>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$?</p>

<p>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$.</p>

<p>(My source was Papadimitriou's book.)</p>

CC BY-SA 2.5
2010-09-02T03:10:00.830Z
2010-09-02T03:10:00.830Z
didest
<p>This is along the lines of "<a href="https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book">Algorithms from the Book</a>". 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!  </p>

<p>Reductions of all kinds are most welcome. </p>

<p>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.</p>

<p>Those who are missing the context of the book may want to look at the question about <a href="https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book">Algorithms from the book</a>. </p>

<p><strong>Update:</strong> 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 :)</p>

<p>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. </p>

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

<p>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 <em>height one</em>. I recall not being able to prove it immediately, although it seems obvious in retrospect.</p>

<p>I suppose <em>obvious in retrospect</em> 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!</p>

CC BY-SA 4.0
2021-02-14T21:28:18.093Z
A somewhat related question has been posted recently: https://cstheory.stackexchange.com/questions/48389/the-graph-of-problem-reductions
Matthieu Latapy
CC BY-SA 2.5
2010-08-31T13:49:59.830Z
Community wiki.
Dave Clarke
CC BY-SA 2.5
2010-08-31T13:53:03.240Z
@supercooldave: Thanks - I suppose I should have done that while posting. My oversight!
Neeldhara
CC BY-SA 2.5
2010-08-31T14:06:41.983Z
@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
CC BY-SA 2.5
2010-08-31T14:26:22.227Z
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
CC BY-SA 2.5
2010-08-31T15:40:40.680Z
@Robin - Thanks for the suggestion, I have now added a longer-than-intended clarification.

@Arnab - Thank you too!
Neeldhara
CC BY-SA 2.5
2010-09-08T11:21:33.557Z
@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
<ds.algorithms><np-hardness><big-list><reductions>
Reductions from the book.
Neeldhara
# Reductions from the book.

(Asked by: username_0 on 2010-08-31)

This is along the lines of "[Algorithms from the Book](https://cstheory.stackexchange.com/questions/189/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](https://cstheory.stackexchange.com/questions/189/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!

**Tags:** ds.algorithms, np-hardness, big-list, reductions
> **Comments:**
> **username_2**: Community wiki.  
> **username_0**: @supercooldave: Thanks - I suppose I should have done that while posting. My oversight!  
> **username_0**: @Jukka: Thanks! I thought that's what supercooldave's edit did. I now realize that edit added a tag. It's now a CW :)  
> **username_3**: 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.  
> **username_0**: @Robin - Thanks for the suggestion, I have now added a longer-than-intended clarification.  @Arnab - Thank you too!  
> **username_4**: @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.  
> **username_1**: A somewhat related question has been posted recently: https://cstheory.stackexchange.com/questions/48389/the-graph-of-problem-reductions  

---

## 8 answers

### Answer by username_5 on 2010-08-31. Score: 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.

> **Comments:**
> **username_0**: 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: http://www.cs.yale.edu/publications/techreports/tr288.pdf  

---

### Answer by username_6 on 2010-09-01. Score: 9

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

* **multiclass classification to binary classification** ([link](http://jmlr.csail.mit.edu/papers/volume1/allwein00a/allwein00a.pdf)) -- one can solve a problem of choosing among many classes by solving easier problems of choosing between two.
* **strong learning to weak learning** ([boosting](http://en.wikipedia.org/wiki/AdaBoost)) -- one can achieve arbitrarily low error rates given the ability to achieve slightly better than random.
* **ranking to classification** ([link](http://hunch.net/~jl/projects/reductions/ranking/journal_final/ranking.pdf))
* **squared loss to classification** ([probing](http://hunch.net/~jl/projects/reductions/probing/aistat_real_final/aistat_final.pdf)) -- one can estimate class membership probabilities by using a classifier with a small error rate.

A [tutorial](http://hunch.net/~reductions_tutorial/) by Alina Beygelzimer, John Langford, and Bianca Zadrozny covers some others.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_7 on 2010-08-31. Score: 8

**Cook-Levin Theorem**

Any problem in NP can be reduced in polytime by a deterministic turing machine to SAT. For reference see [1](http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem).


---

### Answer by username_8 on 2010-09-03. Score: 8

Integer multiplication to fast Fourier transforms!

> **Comments:**
> **username_9**: and the corollary: string matching to FFTs !  

---

### Answer by username_10 on 2010-08-31. Score: 6

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

> **Comments:**
> **username_11**: Rice-Shapiro's generalization is even more beautiful. See Cutland's exposition: http://books.google.com/books?id=wAstOUE36kcC&lpg=PA130&ots=juxGhcu1Xm&pg=PA130#v=onepage&q&f=false)  

---

### Answer by username_7 on 2010-08-31. Score: 3

**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](http://www.soe.ucsc.edu/classes/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf).


---

### Answer by username_7 on 2010-08-31. Score: 3

**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](http://www.shannarasite.org/kb/kbse60.html).

> **Comments:**
> **username_11**: The reduction using NAESAT instead of 3SAT (in Papadimitriou's book) is more direct.  

---

### Answer by username_11 on 2010-09-02. Score: 2

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


---

