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.

$\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
    Commented 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
    Commented 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
    Commented Dec 8, 2021 at 15:03

1 Answer 1

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.

$\endgroup$

Your Answer

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

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