If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?

  • $\begingroup$ Yes, there is a specific complexity class for this type of languages. I think it is called DP if I remember correctly. $\endgroup$
    – nir shahar
    Feb 24 '21 at 0:27
  • $\begingroup$ Let $L=A=B$ and $L \in P$. Then $L = A \cap B$, $A \in NP$, $B \in coNP$, as required in the statement, and you don't need $NP=coNP$ for $L$. $\endgroup$
    – user114966
    Feb 24 '21 at 1:09
  • $\begingroup$ The language $\Sigma^*$ is both in NP and in coNP. If we take $A=B=\Sigma^*$ then we get $L=\Sigma^*$, which is unconditionally both in NP and in coNP. $\endgroup$ Feb 26 '21 at 8:25

No, because $A$ isn't necessarily $NP$-complete and $B$ isn't necessarily $coNP$-complete. You'd need both to be true to force the implication $NP = coNP$ by $X$ being a member of both problem classes. In fact $A$ and $B$ could both be in $NP$ and $coNP$. E.g. $A$ and $B$ could both be in $P$. $NP \cap coNP$ is not the empty set.

  • $\begingroup$ thanks, that makes sense. So if they are both NP-complete/coNP-complete it would indeed imply that NP = coNP? $\endgroup$
    – Friedrich
    Feb 24 '21 at 2:13
  • $\begingroup$ @Friedrich Yes. $\endgroup$
    – Kyle Jones
    Feb 24 '21 at 2:59

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.