1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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, 2018 at 15:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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