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. I created these while studying them back in college. Hopefully, they’ll be helpful for someone.

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 Introduction to Algorithms (or “CLRS” after its authors).

For decision problem $A$ :

$A \in \text{NP-complete} \iff A \in \text{NP} \cap \text{NP-hard}$

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

Showing the problem is in NP

For a decision problem $A$ 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 $A$ can be verified in polynomial time.

Showing the problem is NP-hard

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

$B \leq_\text{P} A$

In other words: $A$ is at least as hard as $B$

Sufficient proofs

Any instance $b$ of $B$ can be reduced to an $a$ instance of $A$ in polynomial time; and
Decision $a$ is “Yes” $\iff b$ 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.