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 [1].
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.
- *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.
Leave a comment