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.