Proving that PP is closed under symmetric difference I want to prove that PP is under symmertic difference.
let A be a language in PP and B likewise.
I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed under union , I should be done.
How do I show A\B in PP?
Am I on the right track? Maybe there is an easier way?
As stated in the Wikipedia article about PP, a proof that PP is closed under symmetric difference was a PhD thesis by David Russo Structural properties of complexity classes. Proving that PP is closed under union was also open for a long time until it was answered by R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991