3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

There are several different definitions of $\mathsf{PP}$. I'll take this one: the class of languages $L$ such that there exists a probabilistic polytime Turing machine $T$ satisfying $$L = \{x : \Pr[T(x)=1] > 1/2\}.$$ Let me stress that the Turing machine is only allowed to toss unbiased coins.

The first step is to show that for every language $L \in \mathsf{PP}$ there exists a probabilistic polytime Turing machine $S$ such that $$ L = \{ x : \Pr[S(x)=1] > 1/2 \}, \\ \overline{L} = \{ x : \Pr[S(x)=1] < 1/2 \}. $$ In other words, $\Pr[S(x)=1] \neq 1/2$ for all $x$. To show this, take the machine $T$ promised above, and suppose that on inputs of length $n$ it runs in time $p(n)$. Thus if $\Pr[T(x)=1] > 1/2$ then $\Pr[T(x)=1] \geq 1/2 + 1/2^{p(n)}$. The new machine will output $T(x) \land B$, where $B$ is a random variable satisfying $\Pr[B=0] = 1/2^{p(n)}$ (we can realize such a variable $B$ in polytime). We have $$ \Pr[S(x)=1] = \left(1 - \frac{1}{2^{p(n)}}\right) \Pr[T(x)=1]. $$ If $x \in L$ then $$ \Pr[S(x) = 1] \geq \left(1 - \frac{1}{2^{p(n)}}\right) \left(\frac{1}{2} + \frac{1}{2^{p(n)}}\right) = \frac{1}{2} + \frac{1}{2^{p(n)+1}} - \frac{1}{2^{2p(n)}} > 1/2. $$ In contrast, if $x \notin L$ then clearly $\Pr[S(x) = 1] < \Pr[T(x)=1] \leq 1/2$.

Armed with this result, let now $A,B \in \mathsf{PP}$, with associated machines $S_A,S_B$, both satisfying the promise above. Our new machine $S$ will output $S_A(x) \oplus S_B(x)$. Using $p_A(x),p_B(x),p(x)$ to denote the probabilities that the machines $S_A,S_B,S$ (respectively) output $1$ on $x$, we have $$ p(x) = p_A(x) (1-p_B(x)) + p_B(x) (1-p_A(x)) = p_A(x) + p_B(x) - 2p_A(x) p_B(x). $$

We now have to consider three cases. Suppose first that $x \in A \Delta B$, say $x \in A$ and $x \notin B$. Then $p_A(x) > 1/2$ and $p_B(x) < 1/2$, and so $$ p(x) = p_A(x) (1-2p_B(x)) + p_B(x) > \frac{1}{2} (1-2p_B(x)) + p_B(x) = \frac{1}{2}. $$ A similar calculation works when $x \notin A$ and $x \in B$. So if $x \in A \Delta B$, we have $p(x) > 1/2$.

Suppose next that $x \in A \cap B$. Then $p_A(x),p_B(x) > 1/2$, and so $$ p(x) = p_B(x) - p_A(x) (2p_B(x) - 1) < p_B(x) - \frac{1}{2} (2p_B(x) - 1) = \frac{1}{2}. $$ Similarly, if $x \notin A \cup B$ then $p_A(x),p_B(x) < 1/2$ and so $$ p(x) = p_A(x) (1 - 2p_B(x)) + p_B(x) < \frac{1}{2} (1 - 2p_B(x)) + p_B(x) = \frac{1}{2}. $$ We conclude that if $x \notin A \Delta B$ then $p(x) < 1/2$.

$\endgroup$

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.