4
$\begingroup$

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. I am looking for some that are solvable in reasonable time, not research-level problems.

Is anyone aware of such list?

EDIT: Just elaborating on what I mean (from the discussion below).

Karp's 21 problems are too well-known, so I have spoilers to most of the answers. In Introduction to theory of computation (by Sipser), I find most of the exercises easy, with 1 or 2 problems in the right level and 2 or 3 problems just very hard (have to eventually look them up). I need exercises harder than most of the exercises in popular textbooks. If a textbook has some exercises that are harder on average than most textbooks, it would be great to know about it.

  • 0
    Doesn't every book on computational complexity contain such a problem list? I guess it does.2012-02-28
  • 0
    http://en.wikipedia.org/wiki/List_of_NP-complete_problems and http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems2012-02-28
  • 0
    "solvable in reasonable time". Can you be more precise?2012-02-28
  • 0
    @DamianSobota The books I have been through usually have very easy exercises with very few harder exercises.2012-02-29
  • 0
    @J.D. I have two things against Karp's 21 NP-complete problems, first, I have already seen most of the solutions, and second, most of them are quite hard to prove (if you've never seen the idea before).2012-02-29
  • 0
    @Aryabhata Let me try to be more precise. Every proof of hardness I have seen so far is either just too easy. I think for 2 minutes and I have it. Or, when I see the solution, I think that there's no way i would have gotten the proof on my own. I am looking for things that fall in the middle.2012-02-29
  • 0
    @aelguindy: Perhaps if you tell what you found too easy and what you found too hard, one can try to tell what _your_ middle ground is. Otherwise, people will just be guessing, as what is easy for your might be hard for someone else etc.2012-02-29
  • 0
    @Aryabhata For instance, in Introduction to Theory of Computation (by Sipser), the exercises following chapter on NP-completeness. Most of the exercises are very easy. One or two exercises were very hard (I had to look up the solutions) and two or so exercises were just about right. I can elaborate with examples once I have my hands on a copy of the book.2012-02-29
  • 0
    In general, I am looking for a list that is on average harder than what is in text books (at least very popular ones). I would also be glad to find a text whose exercises are harder than the others..2012-02-29
  • 2
    @aelguindy: Please edit the examples etc into the question. Not all people read the comments.2012-02-29
  • 0
    I know that this question is too old, however you can consult the book [Computers and Intractibility](http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455). Note that there are no exercises, as far as I remember, but gives you a chance to think more deeply and also references for further explorations.2015-09-02

0 Answers 0