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”


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