According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2.

So, the problem is to prove that if in definition we change probability from 1/2 to any rational number (0,1) we obtain the same class of problems.

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that, and without more to work with, it's hard to know how to help. You might want to take a look at meta.cs.stackexchange.com/q/1284/755 and then edit the question to improve it based on the guidelines there. $\endgroup$
    – D.W.
    Oct 6 '16 at 18:22
  • $\begingroup$ Hint: How do you use such algorithms in practice? $\endgroup$
    – Raphael
    Oct 6 '16 at 19:38

Lets say a separation using $p\in\mathbb{Q}$ exists for $L\subseteq\Sigma^*$ if there exists a polynomial probabilistic Turing machine $M$ such that:

$x\in L \Rightarrow \Pr\left[\text{M accepts x}\right]> p$

$x\notin L \Rightarrow \Pr\left[\text{M accepts x}\right]< p$

$L\in PP$ iff there exists a separation for $L$ using $\frac{1}{2}$ (we can use a strong inequality in both cases). We proceed to show that $\forall p,q\in (0,1)\cap \mathbb{Q}$, if there exists a separation for $L$ using $p$, then there exists a separation using $q$.

We shall use the fact that a probabilistic Turing machine with access to unbiased random coins, is able to simulate an $\alpha$-biased coin for any rational (this can be strengthened) $\alpha\in [0,1]$, in $O(1)$ expected time. See lemma 7.14 in Arora and Barak's book for a proof.

Now, given a machine $M_p$ with separation $p$ for $L$, lets consider a machine $M_q$, which starts by tossing an $\alpha$-biased coin. If the outcome is $1$ then it accepts, otherwise it simulates $M_p$ on the input and returns it's answer.

Since we want $M_q$ to be polynomial in the worst case, we restrict the simulation of the $\alpha$-biased coin to a certain number of iterations, such that the simulation halts with probability $1-\epsilon$ (this can be done for any $\epsilon>0$, simply use the fact that the simulation runs in expected constant time, and apply Markov's inequality). If the simulation didn't halt, $M_q$ accepts. In this case we have:

$\Pr\left[\text{$M_q$ accepts x}\right]=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)\Pr\left[\text{$M_p$ accepts x}\right]\right)$, so:

$x\in L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]> \epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right) $

$x\notin L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]< \epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right) $

This means it is enough to require $q=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)$. Equivalently,


Since $p,q\in (0,1)\cap \mathbb{Q}$, if $q>p$ we can find a small rational $\epsilon$ and rational $\alpha\in (0,1)$ to satisfy this. If $p>q$ you can change $M_q$ to reject when the outcome of the $\alpha$-biased coin is 1. When this equality holds, $M_q$ achieves $q$ separation for $L$ and we are done.


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.