3
$\begingroup$

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? Image describing the problem visually

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Pease check the image that I have attached to the question. I still don't understand how X is reducible to Y. $\endgroup$ – Sai Charan Jun 13 at 17:05
  • $\begingroup$ @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. $\endgroup$ – dkaeae Jun 13 at 18:51
  • $\begingroup$ 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? $\endgroup$ – Sai Charan Jun 14 at 10:15
  • 1
    $\begingroup$ 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! $\endgroup$ – dkaeae Jun 14 at 10:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please check the image that I have attached to the question. I don't think my doubt was clear to everyone. $\endgroup$ – Sai Charan Jun 14 at 10:17
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jun 14 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.