patternMinor
Proving a problem as NP-complete
Viewed 0 times
provingcompleteproblem
Problem
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?
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?
Solution
As you have stated, there are two very clear requirements for a problem $X$ to be $\mathbf{NP}$-complete:
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.
- $X \in \mathbf{NP}$.
- $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.
Context
StackExchange Computer Science Q#110640, answer score: 2
Revisions (0)
No revisions yet.