# 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