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?

  • 1
    $\begingroup$ 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. $\endgroup$ – chi Sep 12 '18 at 8:21

Hint : Construct a poly-time verifier for L1^C by using L2's verifier, in addition to running some polynomial-time checks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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