# How to show a problem is NP-complete

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 .

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.

1. *
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.

## Join the Conversation

1. 