0
$\begingroup$

Possible Duplicate:
Do many-one reductions and Turing reductions define the same class NPC

Hi,

Is the following true:

If L is coNP-hard, then L is NP-hard.

I have found statements of this, but no proofs, so, a reference would be greatly appreciated.

Thank you!

--Katherine

| cite | improve this question | |
$\endgroup$
  • 6
    $\begingroup$ If you're talking about hardness under polynomial-time many-one reductions, then this would imply NP=coNP (which is unknown). If you're talking about polynomial-time Turing reductions, then this is trivially true. $\endgroup$ – Holger Mar 16 '11 at 17:06
  • 2
    $\begingroup$ This may be a possible duplicate of these questions: 1, 2, and 3. Vote to close as a duplicate. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 16 '11 at 17:22