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.
2026-04-03 14:28:28.1775226508
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 Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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$.