This is the first post in a series of posts where I will attempt to give visual, easy to understand, proofs^{*} of NP-completeness for a selection of decision problems. In this post, I will give a “template” which can be used (and will be used for the proofs I post).

I will assume the reader is familiar with decision problems and the complexity classes P, NP and NP-hard. If not, please see the Wikipedia article on NP-completeness, or better yet, take a look in Chapter 34 of [1].

For decision problem :

(1)

In other words, we will need to show that is in NP, and in NP-hard.

### Showing the problem is in NP

For a decision problem to be in NP, it is sufficient to show that a **certificate** (an encoding of a solution to the problem) can be **verified** to represent a solution to the decision problem in polynomial time.

#### Sufficient proof

- Certificate for instance of can be verified in polynomial time.

### Showing the problem is NP-hard

For a decision problem to be NP-hard, it is sufficient to show that any instance of another decision problem , which is **already known to be NP-hard**, can be reduced to an instance of , such that the reduction of into can be performed in polynomial time. We express the existence of such a reduction as:

(2)

In other words: is at least as hard as

#### Sufficient proofs

- Any instance of can be reduced to an instance of in polynomial time; and
- Decision is “Yes” is “Yes”

### Conclusion

Using knowledge about other problems already proven to be NP-complete, and some creativity, we are now ready to attempt proving NP-completeness.

^{*}The series is a spin-off of some work I did in order to prepare for an exam. I will attempt to be as rigorous and correct as I can, within reason. The main purpose of the series is to give intuition, which the reader can then use to develop rigor, if desired.

- [1]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and S. Clifford,
*Introduction to Algorithms*. MIT Press, 2009.

## Leave a comment