2
$\begingroup$

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.

  • 1
    What happens when $L_1 = L_2$?2011-11-01

1 Answers 1

1

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$.

  • 0
    $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.2011-11-03