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.