<p>Two suggestions:</p>

<ul>
<li><p>On a historical note, look at Karp's <a href="http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" rel="nofollow">paper</a> "Reducibility Among Combinatorial Problems", which gives 21 NP-complete problems. This paper showed that many well-known problems were NP-complete for the first time, and gave clever reductions between them.</p></li>
<li><p><a href="http://www-math.mit.edu/~sipser/book.html" rel="nofollow">Introduction to the Theory of Computation</a> by Michael Sipser has a nice collection of reduction exercises between NP-complete problems in the time complexity chapter.</p></li>
</ul>

CC BY-SA 2.5
2011-02-11T13:19:29.853Z
I had Introduction to the Theory of Computation at arm reach while writing the question. We used it in my first theoretical computer science course but never covered it completely. I'm reading through that chapter right now. Thanks a lot.
tmoisan
CC BY-SA 2.5
2011-02-11T04:59:09.333Z
2011-02-11T04:59:09.333Z
Huck Bennett
<p>A good start is <a href="http://rads.stackoverflow.com/amzn/click/0716710455" rel="nofollow noreferrer">Computers and Intractability: A Guide to the Theory of NP-Completeness</a> by Garey and Johnson. Chapter 3.2 discusses techniques and 3.3 has exercises. You can find more in the <a href="https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3258#3258">books about complexity everyone should read</a>.</p>

CC BY-SA 2.5
2011-02-11T07:36:01.040Z
I'd second this. I've used G&J for lottery day at my class: students get to choose problems out of a bag and have to show that they are NP-hard :)
Suresh Venkat
CC BY-SA 2.5
2011-02-12T02:29:23.480Z
Thanks for the pointers. I'll check this book from my university library very soon.
tmoisan
CC BY-SA 2.5
2011-02-11T00:39:54.010Z
2011-02-11T00:39:54.010Z
2017-04-13T12:32:28.053Z
Marcus Ritt
<p>I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), mostly including gadgets. However the course has very few exercises to practice ourselves and the teacher is reluctant to give us some more. Is there any resources, web or books, that could fill this gap for me? I'm talking about problems and possibly their solutions and some explanation about the process of finding the reduction.</p>

<p>Thanks.</p>

CC BY-SA 2.5
2011-02-12T16:18:34.547Z
I appreciate the question, but it is offtopic as per our FAQ, isn't it?
Raphael
CC BY-SA 2.5
2011-02-16T20:51:19.097Z
@Raphael : I've read the FAQ and I don't see where I'm offtopic. Is my question too basic? If so where should I have asked it? The answers here refer to another question on the site so I guess it's at the right level.
tmoisan
CC BY-SA 2.5
2011-02-16T22:19:19.840Z
Since this kind of reduction got covered in my second year of undergrad studies, I assumed it to be low-level, yes. Apparently our (quite zealous) inquisitors disagree, so you should be fine. I would have asked my teacher for more exercises.
Raphael
<cc.complexity-theory><reference-request><np-hardness><reductions>
Exercises of polynomial and turing reductions
tmoisan
# Exercises of polynomial and turing reductions

(Asked by: username_0 on 2011-02-11)

I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), mostly including gadgets. However the course has very few exercises to practice ourselves and the teacher is reluctant to give us some more. Is there any resources, web or books, that could fill this gap for me? I'm talking about problems and possibly their solutions and some explanation about the process of finding the reduction.

Thanks.

**Tags:** cc.complexity-theory, reference-request, np-hardness, reductions

> **Comments:**
> **username_1**: I appreciate the question, but it is offtopic as per our FAQ, isn't it?  
> **username_0**: @username_1 : I've read the FAQ and I don't see where I'm offtopic. Is my question too basic? If so where should I have asked it? The answers here refer to another question on the site so I guess it's at the right level.  
> **username_1**: Since this kind of reduction got covered in my second year of undergrad studies, I assumed it to be low-level, yes. Apparently our (quite zealous) inquisitors disagree, so you should be fine. I would have asked my teacher for more exercises.  

---

## 2 answers

### Answer by username_3 on 2011-02-11. Score: 7 | Accepted answer

A good start is [Computers and Intractability: A Guide to the Theory of NP-Completeness](http://rads.stackoverflow.com/amzn/click/0716710455) by Garey and Johnson. Chapter 3.2 discusses techniques and 3.3 has exercises. You can find more in the [books about complexity everyone should read](https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3258#3258).

> **Comments:**
> **username_4**: I'd second this. I've used G&J for lottery day at my class: students get to choose problems out of a bag and have to show that they are NP-hard :)  
> **username_0**: Thanks for the pointers. I'll check this book from my university library very soon.  

---

### Answer by username_2 on 2011-02-11. Score: 4

Two suggestions:

* On a historical note, look at Karp's [paper](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf) "Reducibility Among Combinatorial Problems", which gives 21 NP-complete problems. This paper showed that many well-known problems were NP-complete for the first time, and gave clever reductions between them.
* [Introduction to the Theory of Computation](http://www-math.mit.edu/~sipser/book.html) by Michael Sipser has a nice collection of reduction exercises between NP-complete problems in the time complexity chapter.

> **Comments:**
> **username_0**: I had Introduction to the Theory of Computation at arm reach while writing the question. We used it in my first theoretical computer science course but never covered it completely. I'm reading through that chapter right now. Thanks a lot.  

---

