I want to prove that the below assertion is false:
Given L1,L2 $\in$ co-NP, does L1 $\cap$ L2 $\in$ NP ?
I already know that co-NP is closed under intersection and union, but this result is not useful since the membership in co-NP doesn't exclude the membership in NP. I tried to figure out how the things work in the 3 different cases:
- L1,L2 $\in$ co-NP $\cap$ NP : trivially true
- L1 $\in$ co-NP $\cap$ NP , L2 $\in$ co-NP$\setminus$NP : ?
- L1,L2 $\in$ co-NP$\setminus$NP : in other words, co-NP$\setminus$NP is closed under intersection?
Is there a way to prove the incorrectness of this assertion? Or can you provide a counterexample? Thanks.
NB: I'm assuming that L1 $\neq$ L2, since I want the most general case.
You could consider $L_1$ and $L_2$ to be $coNP$-complete languages. In that case we don't know if $L_1 \cap L_2 \in NP$. That would imply $coNP = NP$, which is currently unknown. (ofers implication of $L \in P$ is as far as I can see incorrect).
Your question can be rephrased to the problem of $NP$ vs $coNP$, hence whether $NP$ is closed under complement. Though a highly researched question (a negative answer would solve $P$ vs $NP$), we don't know the answer to that one yet. So at the current point of research, your question must be answered with unknown, though it is believed that $NP \neq coNP$.