1
$\begingroup$

This question already has an answer here:

I have been confusing a bit about these relationship:

Given A polynomial reducible to B

1/ If A is NP hard, what is the hardness of B?

2/ If B is NP hard, what is the hardness of A?

3/ If A has polynomial algorithm, how is B?

4/ If B has polynomial algorithm, how is A?

Since "B is as hard as A", then for 1/, we can say B is also NP Hard. However, I'm not sure about the reverse order. In 2/, there is not enough evidence to conclude the hardness of A

Also, for 4/ If B has poly algorithm, then A also has a poly algorithm. I'm thinking 3/ is also similar, since A is reducible to B and B as hard as A, if A has poly algorithm so does B.

Can someone please verify this? Thanks very much

$\endgroup$

marked as duplicate by David Richerby complexity-theory May 2 '18 at 16:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Hint: problems in P are polynomially reducible to SAT. SAT (satisfiability problem) is NP-hard. Does that mean SAT is also in P? $\endgroup$ – Auberon Apr 30 '18 at 15:41
0
$\begingroup$

If a problem $A$ is reduced to $B$, this implies that an algorithm $\mathbb{A}$ that solves $B$ can also solve $A$.

If $\mathbb{A}$ is a polynomial-time algorithm, then $B \in \mathbf{PTIME}$ and also $A \in \mathbf{PTIME}$.

If it is the case that when $\mathbb{A}$ is polynomial-time algorithm, this implies that $\mathbf{P} = \mathbf{NP}$, then $B$ is an $\mathbf{NP}\text{-hard}$ problem. Which means $A$ is also an $\mathbf{NP}\text{-hard}$ problem.

These statements answer questions 1, 2, and 4. However, your third question cannot be answered with the information you provided. This is because any problem in PTIME is also in NP, and therefore having a polynomial-time algorithm does not necessarily mean that $B$ has a polynomial-time algorithm. It might or might not have.

$\endgroup$

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