# Proving a problem as NP-complete

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is:

Do we also need to prove that problem X can be reduced to at least one NP problem?

According to the definition of NP-completeness, each and every NP problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete?

As you have stated, there are two very clear requirements for a problem $$X$$ to be $$\mathbf{NP}$$-complete:

1. $$X \in \mathbf{NP}$$.
2. $$X$$ is $$\mathbf{NP}$$-hard. That is, for every $$Y \in \mathbf{NP}$$, $$Y$$ is (poly-time many-one) reducible to $$X$$.

Do we also need to prove that problem $$X$$ can be reduced to at least one $$\mathbf{NP}$$ problem?

No, as this is not one of the above requirements. However, if you are able to do so, you've proved that $$X \in \mathbf{NP}$$ (i.e., requirement no. 1): Suppose $$X$$ is reducible to $$Y \in \mathbf{NP}$$. Then verifying $$x \in X$$ can be done in poly-time by reducing $$x$$ to an instance $$y$$ of $$Y$$ and then verifying $$y \in Y$$.

As problem $$X$$ is $$\mathbf{NP}$$, are we not supposed to prove that this $$\mathbf{NP}$$ problem can be reduced to other $$\mathbf{NP}$$-complete problems?

There is no need to. If you know $$Y$$ is $$\mathbf{NP}$$-complete and you show $$X \in \mathbf{NP}$$, then necessarily $$X$$ is reducible to $$Y$$. There is no need for you to do "extra" work.

Why does this reduction have to be only one way to prove a problem is $$\mathbf{NP}$$-complete?

I am afraid I am not quite sure which reduction you are referring to, but if you are talking about reducing $$X$$ to $$Y$$, then the answer is simply: That is what the definition of $$\mathbf{NP}$$-completeness requires you to do.

• Pease check the image that I have attached to the question. I still don't understand how X is reducible to Y. – Sai Charan Jun 13 '19 at 17:05
• @SaiCharan What is missing in your picture is an arrow from x to y in the second diagram. You have established x is in NP, so it is reducible to y for the exact same reason a, b, and c are. – dkaeae Jun 13 '19 at 18:51
• I still don't get it. a,b,c were reducible to y because they were proved explicitly. Does this mean I also need to prove that x is reducible to y? – Sai Charan Jun 14 '19 at 10:15
• If you've proved only a, b, and c are reducible to y, then you've done something wrong. There are infinitely many problems in NP, so you can't just reduce them one by one to y. Also, if y is NP-complete, then any problem in NP is reducible to it, whether you're aware of its existence or not! – dkaeae Jun 14 '19 at 10:44

Do we also need to prove that problem X can be reduced to at least one NP problem?

No. Every problem in NP can be reduced to some problem in NP: namely, to itself. "Can be reduced to at least one NP problem" isn't a part of the definition of NP-completeness, so you don't need to prove it. You just need to prove the things required by the definition.

• Please check the image that I have attached to the question. I don't think my doubt was clear to everyone. – Sai Charan Jun 14 '19 at 10:17
• The definition of $L$ being NP complete is that (1) $L$ is in NP and (2) every problem in NP reduces to $L$. To prove that something is NP-complete, you need to prove (1) and (2) and nothing else. – David Richerby Jun 14 '19 at 13:59