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.


  • $\begingroup$ I appreciate the question, but it is offtopic as per our FAQ, isn't it? $\endgroup$ – Raphael Feb 12 '11 at 16:18
  • $\begingroup$ @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. $\endgroup$ – tmoisan Feb 16 '11 at 20:51
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 16 '11 at 22:19

A good start is Computers and Intractability: A Guide to the Theory of NP-Completeness 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.

  • 1
    $\begingroup$ 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 :) $\endgroup$ – Suresh Venkat Feb 11 '11 at 7:36
  • $\begingroup$ Thanks for the pointers. I'll check this book from my university library very soon. $\endgroup$ – tmoisan Feb 12 '11 at 2:29

Two suggestions:

  • On a historical note, look at Karp's paper "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 by Michael Sipser has a nice collection of reduction exercises between NP-complete problems in the time complexity chapter.

  • $\begingroup$ 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. $\endgroup$ – tmoisan Feb 11 '11 at 13:19

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.