# If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

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?

• Yes, there is a specific complexity class for this type of languages. I think it is called DP if I remember correctly. Feb 24 '21 at 0:27
• 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$.
– user114966
Feb 24 '21 at 1:09
• 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. 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.