# Reducible and NP Hard [duplicate]

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

## marked as duplicate by David Richerby complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 2 '18 at 16:47

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

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.