Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?
If $B$ is NP-hard then $A$ is NP-hard.
Can some explain this intuitively?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ @Steven wow you means this is open problem? $\endgroup$ – Betty Andersson Jan 11 at 1:32
-
$\begingroup$ @Steven would you please take an example for me from classic problem to better intuitive idea? $\endgroup$ – Betty Andersson Jan 11 at 1:34
-
$\begingroup$ Please don't delete your question after it has received an answer. Part of our mission is to build up an archive of questions and answers that will be useful to others in the future. $\endgroup$ – D.W.♦ Jan 17 at 7:06
-
$\begingroup$ Does this answer your question? surprizing reducibility and challenge on it $\endgroup$ – Bader Abu Radi Jan 18 at 9:22
-
1$\begingroup$ A question should not be duplicated. In fact, you asked it before, I don't see what you gain by asking it again. $\endgroup$ – Bader Abu Radi Jan 18 at 9:25
Add a comment
|
$\begingroup$
$\endgroup$
1
Let $B$ be a $\mathsf{NP}$-hard problem and $A=\emptyset$. Then $A \le_p B$ (the reduction just maps any instance of $A$ to some fixed "no" instance of $B$). However $A$ cannot be $\mathsf{NP}$-hard since there is no Karp reduction from $\Sigma^* \in \mathsf{NP}$ to $A$.
-
1$\begingroup$ is it possible make it more sensible and simple? via an example? $\endgroup$ – Betty Andersson Jan 11 at 1:44
$\begingroup$
$\endgroup$
1
B being NP-hard does not say anything about A. The problem says that there is a way to reduce A to B in polynomial time.
But on the other hand, it is also not given that A getting reduced to B is the only pathway for solving A. So, there can be other ways of solving A in polynomial time.
Hence, the implication that A is NP-hard is false.
-
$\begingroup$ To show that the implication is false, you need to give a counterexample. $\endgroup$ – Yuval Filmus Feb 21 at 8:38
$\begingroup$
$\endgroup$
Suppose that all problems in the world could be ranked in terms of difficulty, where higher numbers correspond to more difficult problems.
If $B$ is NP-hard then its ranking is large, $r(B) \geq M$.
If $A$ reduces to $B$ then $A$ is not harder than $B$, that is, $r(A) \leq r(B)$.
Given $r(B) \geq M$ and $r(A) \leq r(B)$, can you conclude any lower bound on $r(A)$?
Concretely, if $r(A) = 0$ then $r(A) \leq r(B)$ yet $r(A) \not\geq r(B)$. This can be realized in the real world by choosing $A$ to be some trivial problem, such as the empty language (all instances are No instances) or the complete language (all instances are Yes instances). Trivial languages are trivially reducible to any language, but they are so trivial that we can be sure that they are not NP-hard (for technical reasons).
If we disallow trivial languages, then we can still take $A$ to be any language in P. Since P is a subset of NP, we know that $A$ reduces to $B$ (this can also be seen directly – a reduction can simply solve $A$ and output one of two fixed instances of $B$), but assuming that P≠NP, $A$ is not NP-hard.
Is the assumption P≠NP really necessary? If P=NP and $A$ is non-trivial then $A$ is trivially NP-hard, since all language in P trivially reduces to any non-trivial language.
answered Feb 21 at 8:51
$\begingroup$
$\endgroup$
2
Problem: Is a = b? Reduction to bin packing: Assume you have bins of size (a+b)/2. Can one item of size a and one item of size b be packed into 2 bins?
We just reduced a very, very simple problem to an NP-complete problem.
-
$\begingroup$ This is not a valid example since, as far as we know, the problem "Is $a=b$?" might be $\mathsf{NP}$-hard. Indeed, if $\mathsf{P}=\mathsf{NP}$ any problem in $\mathsf{NP}$ can be Karp-reduced to any non-trivial problem in $\mathsf{P}$, i.e., every non-trivial problem in $\mathsf{P}$ is NP-hard. $\endgroup$ – Steven Feb 21 at 23:44
-
$\begingroup$ Well, it explains it intuitively. Anyone who gets the explanation intuitively should then be able to create a formal proof, but it's likely not necessary. $\endgroup$ – gnasher729 Feb 23 at 10:54
