3
$\begingroup$

Assume that Problem $A$ is polynomial-time reducible to problem $B$.

Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard.

Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard.

Claim 1 is obviously true, but why the second one is false?

$\endgroup$
3
  • $\begingroup$ What happens when A is "really really easy" compared to B? $\endgroup$ – VashTheStampede Jan 8 at 23:03
  • 2
    $\begingroup$ Yup, therefore (unless P=NP) any problem in P can be a candidate to be such a non-nphard A $\endgroup$ – VashTheStampede Jan 8 at 23:07
  • $\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:08
1
$\begingroup$

I am assuming that $A$ is a non-trivial problem. If $A$ is trivial, then the claims cannot be correct in their current form (make sure you understand why).

Consider an NP-complete problem $B$, and consider some non-trivial problem $A \in \text{P}$. Clearly, $A\leq_p B$. If we assume that claim 2 is correct, then as $A\leq_p B$, we get that $A$ is $\text{NP}$-hard and thus for every problem $L\in \text{NP}$, it holds that $ L\leq_p A$. Hence, as $A\in \text{P}$, we get that $L\in \text{P}$ as well, and so $\text{NP}\subseteq \text{P}$. Conversely, if we assume that $\text{NP}\subseteq \text{P}$, then as every non-trivial problem is $\text{P}$-hard, we get that every non-trivial problem $A$ is $\text{NP}$-hard. Hence, claim 2 holds trivially.

So we have in total that claim 2 is correct iff $\text{P} = \text{NP}$ which is quite open.

$\endgroup$
4
  • $\begingroup$ Yes, and the answer formalizes this intuition. As you know nothing about $A$ and its relation with problems in NP, then claim 2 actually suggests that every non-trivial language is NP-hard, which is the same as suggesting that P=NP. $\endgroup$ – Bader Abu Radi Jan 8 at 23:57
  • $\begingroup$ Yes, NP-complete problems are NP-hard problems in NP. $\endgroup$ – Bader Abu Radi Jan 9 at 0:05
  • $\begingroup$ We proved in the answer that 2 is correct iff P = NP. The P vs NP is an open problem. So the answer to your question, it is unknown whether calim 2 is correct, and knowing the status of claim 2 solves a long standing open problem. Yet, most experts believe that $\text{P} \neq \text{NP}$. Under the assumption that $\text{P} \neq \text{NP}$, the answer proves that 2 is not correct (B in the above answer can be any classic NP-complete problem). $\endgroup$ – Bader Abu Radi Jan 9 at 0:21
  • $\begingroup$ Yes, the answer shows that claim 2 is equivalent to the P vs NP question. $\endgroup$ – Bader Abu Radi Jan 9 at 0:24

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.