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.