Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Doesn't every book on computational complexity contain such a problem list? I guess it does. – Damian Sobota Feb 28 '12 at 23:14
"solvable in reasonable time". Can you be more precise? – Aryabhata Feb 28 '12 at 23:58
@DamianSobota The books I have been through usually have very easy exercises with very few harder exercises. – aelguindy Feb 29 '12 at 7:23
@aelguindy: Please edit the examples etc into the question. Not all people read the comments. – Aryabhata Feb 29 '12 at 7:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.