Given $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$, how do I express L as a symmetric difference of 2 sets in NP?

21 Views Asked by At

My ultimate goal is to show that $L \in PP$, but I need to figure out the title question first as an intermediary step. Any help is appreciated, thanks in advance.

1

There are 1 best solutions below

0
On

Recall that NP is closed under intersection. Hence $L_1\cap\overline{L_2}$ is in NP. Finally we can realize that the symmetric difference of this set and $L_1$ is exactly $L_1\cap L_2$.