An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.)

So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would that means that P=NP?

I think yes (I am almost sure) but I can't find the reason why?

  • 1
    $\begingroup$ " I can't find the reason why?" Have you tried looking at the definition of NP-hard? $\endgroup$ – jmite Mar 5 '16 at 23:12
  • $\begingroup$ And you think I did not look for the definition of NP-hard? $\endgroup$ – drzbir Mar 5 '16 at 23:15
  • $\begingroup$ @ Dr W : I know the definition of P, NP, NP-complete and NP hard. The question you put does not answer my question. $\endgroup$ – drzbir Mar 5 '16 at 23:34
  • $\begingroup$ It follows immediately from the definition of NP-hard. A problem is NP hard if it is polytime reducible from every problem in NP. This literally means that, if an NP-hard problem is in P, every problem in NP is also in P, because that's what a polynomial time reduction is. It's not a theorem that needs to be proved or explained, it is true by definition, which is why we kept pointing you at the definition. $\endgroup$ – jmite Mar 5 '16 at 23:39

Your conclusion is correct: Since an NP-complete problem exists that can be reduced to your NP-hard problem, if you should be able to solve your NP-hard problem in polynomial time the NP-complete problem would be in P, hence P=NP.

| cite | improve this answer | |
  • $\begingroup$ If an NP-hard problem is in NP, then why isn't it NP-complete? $\endgroup$ – drzbir Mar 5 '16 at 23:15
  • $\begingroup$ You are right, an NP-hard problem might not be in NP. But it does not need to be, since NP-complete is a subset of NP-hard AFAIK. $\endgroup$ – choeger Mar 5 '16 at 23:20
  • $\begingroup$ Yeah, this is factually incorrect. An NP-complete problem is in NP by definition, the definition of NP hard is that the problem is polytime reducible to every NP problem. $\endgroup$ – jmite Mar 5 '16 at 23:35
  • 1
    $\begingroup$ @Blid if an NP-hard problem is in NP then it IS NP-complete $\endgroup$ – Albert Hendriks Mar 6 '16 at 13:30

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