<p>No such implication is known.  In particular it may be that $L \ne P = NP$ in which case all problems (including trivial ones) are NP-hard under poly-time reductions (as the reduction can just solve the problem), but trivial ones (in particular ones that lie in L) are surely not P-hard under logspace reductions (as otherwise L=P).  </p>

<p>The same goes for NC instead of L.</p>

CC BY-SA 2.5
2011-03-11T15:13:20.183Z
Thanks very much for this answer.  I think for a lot of people -- and at least for me -- this question seemed like not a big deal, but after reading your three sentence answer, it is "obviously" deep.  (Also, thanks for the question, @Adam Crume.)
Aaron Sterling
CC BY-SA 2.5
2011-03-10T05:11:54.033Z
2011-03-10T05:11:54.033Z
Noam
<p>If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)?  It seems intuitive that if it is as hard as any problem in NP that it should be as hard as any problem in P, but I don't see how to chain the reductions and get a log space (or NC) reduction.</p>

CC BY-SA 2.5
2011-03-10T08:26:20.193Z
This holds if you use the same kind of reductions for both sides, e.g. a $\mathbf{NP-hard}$ problem w.r.t. log-space reductions is also $\mathbf{P-hard}$ w.r.t. log-space reductions.
Kaveh
CC BY-SA 2.5
2011-03-10T09:15:31.290Z
i.e. your intuition is correct but the question you have asked asks for more than that (since you are using different kinds of reduction).
Kaveh
CC BY-SA 2.5
2011-03-10T11:57:29.780Z
The most important part of the question is which notions of reducibility you use, but this information is somehow put in parentheses as if it is the least important information!
Tsuyoshi Ito
<cc.complexity-theory><np-hardness>
Does NP-hardness imply P-hardness?
Adam Crume
# Does NP-hardness imply P-hardness?

(Asked by: username_0 on 2011-03-10)

If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)? It seems intuitive that if it is as hard as any problem in NP that it should be as hard as any problem in P, but I don't see how to chain the reductions and get a log space (or NC) reduction.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: This holds if you use the same kind of reductions for both sides, e.g. a $\mathbf{NP-hard}$ problem w.r.t. log-space reductions is also $\mathbf{P-hard}$ w.r.t. log-space reductions.  
> **username_1**: i.e. your intuition is correct but the question you have asked asks for more than that (since you are using different kinds of reduction).  
> **username_2**: The most important part of the question is which notions of reducibility you use, but this information is somehow put in parentheses as if it is the least important information!  

---

## 1 answers

### Answer by username_3 on 2011-03-10. Score: 32 | Accepted answer

No such implication is known. In particular it may be that $L \ne P = NP$ in which case all problems (including trivial ones) are NP-hard under poly-time reductions (as the reduction can just solve the problem), but trivial ones (in particular ones that lie in L) are surely not P-hard under logspace reductions (as otherwise L=P).

The same goes for NC instead of L.

> **Comments:**
> **username_4**: Thanks very much for this answer.  I think for a lot of people -- and at least for me -- this question seemed like not a big deal, but after reading your three sentence answer, it is "obviously" deep.  (Also, thanks for the question, @Adam Crume.)  

---

