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