Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
What happens when $L_1 = L_2$? –  mhum Nov 1 '11 at 14:54
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
    
You convinced me of the correctness of your answer but I still don't know how/why you state "we don't know if L1∩L2 ∈ NP"... I miss this important implication... Thanks a lot. –  Josh Vorney Nov 2 '11 at 20:08
    
$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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.