Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper

How to set up an NP-completeness proof

(Edited to add: See the comments for some other, better approaches to steps 3 and 4.)

We have a B501 final on Wednesday, and I've talked to a few people in our class who are confused about how to set up an NP-completeness reduction proof. There seems to be a lot of misinformation floating around about what gets reduced to what and what gets reduced from what and so on and so forth. So, here's a handy template. I hope it helps someone.

To show that problem NEW-PROBLEM is NP-complete:

  1. Show that NEW-PROBLEM is verifiable in polynomial time. That is, given a supposed solution, you must be able to tell that it's actually a solution in polynomial time.1
  2. Consider some known NP-hard problem, OLD-PROBLEM. Given any instance OLD-INSTANCE of OLD-PROBLEM, show how to construct, in polynomial time, a corresponding instance NEW-INSTANCE of NEW-PROBLEM, such that NEW-INSTANCE satisfies NEW-PROBLEM exactly when OLD-INSTANCE satisfies OLD-PROBLEM.2
  3. Suppose that we knew of a polynomial-time algorithm A for deciding NEW-PROBLEM. If we did, we would now be able to convert any instance of OLD-PROBLEM into an instance of NEW-PROBLEM using our handy construction technique from step 2, and then solve it using A. Therefore, we would have a polynomial-time algorithm for OLD-PROBLEM.
  4. But we already know that OLD-PROBLEM is NP-hard! Therefore, our supposition in step 3 is wrong, and we must not know of a polynomial-time algorithm for deciding NEW-PROBLEM. Since NEW-PROBLEM is both verifiable in polynomial time and reducible to an NP-hard problem, NEW-PROBLEM is NP-complete.

Notice that steps 3 and 4 stay the same, regardless of what you do in step 2. Step 2 is the meat of the proof, and it's the only step that ever really changes. Indeed, after you have a construction and you've shown that it works, something like "OLD-PROBLEM is polynomial-time reducible to NEW-PROBLEM, hence NEW-PROBLEM is NP-complete" will probably suffice for the rest of the proof. Still, I think it's helpful to remember why you're doing a reduction: you're showing that NEW-PROBLEM must be NP-hard, because for it to be otherwise would be a contradiction.

There's no magic way to make step 2 less hard, but if you can memorize what steps 3 and 4 are all about, then with luck, step 2 will drop in neatly, and you won't start freaking out halfway through about whether you're doing the reduction backwards or something.

That's it. Let me know if I've made any mistakes!

  1. This step of the proof is independent of the others, and you could also do it last, but I like to get it out of the way right away.
  2. This is a polynomial-time reduction from OLD-PROBLEM to NEW-PROBLEM.
Tags: b501

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded