# 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”

## Conclusion

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