1
$\begingroup$

  1. if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?

  2. on the contrary, if A be an NP-complete problem, and B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?

My intuition is, (which may be very wrong), for (1) there are some problems, which are not in NP but are still NP Hard. In that case, wouldn't that make the first statement false? Since a basic requirement for a problem to be in NPC is that the problem should belong to NP Hard first.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ There seems to be a mixup in part 2? Should you swap A and B in the final sentence? $\endgroup$
    – Pål GD
    Dec 8, 2021 at 9:06
  • 1
    $\begingroup$ Does this answer your question? What is the definition of P, NP, NP-complete and NP-hard? $\endgroup$
    – Pål GD
    Dec 8, 2021 at 10:09
  • $\begingroup$ @PålGD Thanks for answering. The part 2 is as is. My intuition behind it, is that since npc is already required to be an NP hard problem, then if A is polynomial time solvable(PTS) then B will also be PTS? $\endgroup$
    – Joe
    Dec 8, 2021 at 15:03

1 Answer 1

Reset to default
1
$\begingroup$

When you hear B is NP-hard, you can consider B being undecidable. If P = NP, then B is still undecidable.

If A is NP-complete and B is NP-hard, and B polynomial time solvable, then, yes, recall:

  • if X is NP-hard, then for every problem Y in NP, there exists a polynomial time reduction from Y to X.

It follows that then A must be polynomial time solvable too.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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