0
$\begingroup$

Can a problem be both NP-Hard and CoNP?

Can a problem be both NP and CoNP-Hard?

$\endgroup$
  • $\begingroup$ no, unless P = NP $\endgroup$ – John Dvorak Oct 6 '13 at 3:06
  • $\begingroup$ I do not think so. NP=CoNP is a first level complexity hierarchy issue. What you are stating is second level. Inferring something at the second level from the first level does not seem logical. $\endgroup$ – T.... Oct 6 '13 at 3:09
  • $\begingroup$ Wouldn't NP = coNP do it? If NP = coNP, than any NP-complete problems is both NP-hard and in coNP. And as far as I know, NP = coNP does not imply P = NP. $\endgroup$ – Peter Shor Oct 6 '13 at 3:12
  • $\begingroup$ @PeterShor that is what I was explaining here. I am just seeing the possibility what if the problem is in CoNP and NP-hard but not in NP? Do we have a choice here like that? That is the question. $\endgroup$ – T.... Oct 6 '13 at 3:15
5
$\begingroup$

There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.

The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

$\endgroup$
  • $\begingroup$ ah ic the problem does not have to be in NP (got it) and thankyou. $\endgroup$ – T.... Oct 6 '13 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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