patternMinor
Proving that PP is closed under symmetric difference
Viewed 0 times
provingsymmetriccloseddifferenceunderthat
Problem
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?
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?
Solution
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
Context
StackExchange Computer Science Q#59823, answer score: 5
Revisions (0)
No revisions yet.