(*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:**

- 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} - 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} - 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*. - 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!

- 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.
- This is a
*polynomial-time reduction from**OLD-PROBLEM**to**NEW-PROBLEM*.