# co-NP assertion

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:

1. L1,L2 $\in$ co-NP $\cap$ NP : trivially true
2. L1 $\in$ co-NP $\cap$ NP , L2 $\in$ co-NP$\setminus$NP : ?
3. 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.

-
What happens when $L_1 = L_2$? – mhum Nov 1 '11 at 14:54

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$.
Thanks for your accurate answer, I had a similar intuition but I was not sure. You wrote that "we don't know if L1∩L2 ∈ NP": is this because the set of co-NP complete languages is not closed under intersection? If it were closed, we could definitely state that L1∩L2 $\notin$ NP ( according to the current world view ), isn't it? – Josh Vorney Nov 1 '11 at 16:18
$coNP$-complete languages are not closed under intersection, hence we can imply everything on the assumption they were. But why don't we know that $L_1 \cap L_2 \in NP$? Because some intersections of $coNP$-complete languages still are $coNP$-complete. Simple case: Take $UNSAT$, a $coNP$-complete language. Then $L_1 := UNSAT \cup \{ (a) \}$ and $L_2 := UNSAT \cup \{ (\neg a) \}$. Both $L_1$ and $L_2$ are still $coNP$-complete. But as $L_1 \cap L_2 = UNSAT$ is $coNP$-complete, $L_1 \cap L_2 \in NP$ if and only if $NP = coNP$. I hope that helps. – Mike B. Nov 3 '11 at 12:05