# If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP

Given $$L_1, L_2 \in \mathsf{NP}$$, $$L_1 \cup L_2 \in \mathsf{P}$$ and $$L_1 \cap L_2 \in \mathsf{P}$$,

Prove: $$\ L_1, L_2 \in \mathsf{coNP}$$

What I've done so far is:

$$L_1 \cup L_2 \in \mathsf{P} \Rightarrow (L_1 \cup L_2) ^\complement \in \mathsf{P} \Rightarrow L_1^\complement \cap L_2^\complement \in \mathsf{P}$$

$$L_1 \cap L_2 \in \mathsf{P} \Rightarrow (L_1 \cap L_2) ^\complement \in \mathsf{P} \Rightarrow L_1^\complement \cup L_2^\complement \in \mathsf{P}$$

How do I proceed from here?

• Draw a little Venn diagram. The complement of $L1$ should be the union of some parts in that, and hopefully that will provide some intuition. – chi Sep 12 '18 at 8:21

Hint: You only need to distinguish between two non-trivial cases: $x\in (L_1\setminus L_2)$ and $x\in L_2\setminus L_1$. In these cases, membership-certificates for $L_1$ would be nonmembership-certificates for $L_2$ and vice versa. Hence, you always have nonmembership-certificates for every input string $x$. And conclude that both $L_1$ and $L_2$ are in $\mathrm{co}$-$\mathrm{NP}$.