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. 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 A:

(1)   \begin{equation*}A \in \textsc{NP-complete} \iff A \in \textsc{NP} \cap \textsc{NP-hard}\end{equation*}

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:

(2)   \begin{equation*} B \leq_\text{P} A \end{equation*}

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.


  1. *
    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. [1]
    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and S. Clifford, Introduction to Algorithms. MIT Press, 2009.

Join the Conversation

3 Comments

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.