3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I appreciate the question, but it is offtopic as per our FAQ, isn't it? $\endgroup$
    – Raphael
    Commented Feb 12, 2011 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
    Commented Feb 16, 2011 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
    Commented Feb 16, 2011 at 22:19

2 Answers 2

Reset to default
7
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Feb 11, 2011 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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