Can a problem be both NP-Hard and CoNP?
Can a problem be both NP and CoNP-Hard?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ no, unless P = NP $\endgroup$– John DvorakCommented Oct 6, 2013 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$– TurboCommented Oct 6, 2013 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 ShorCommented Oct 6, 2013 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$– TurboCommented Oct 6, 2013 at 3:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ ah ic the problem does not have to be in NP (got it) and thankyou. $\endgroup$– TurboCommented Oct 6, 2013 at 3:17