Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am confused about how PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions correct:
$BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \}$
$PP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] > \frac{1}{2} \}$

If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions.

Some concrete examples with clear insight into the subtle points would be very helpful.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

That looks correct to me. The difference between BPP and PP is that for BPP the probability has to be greater than $1/2$ by a constant, whereas for PP it could be $1/2+ 1/2^n$. So for BPP problems you can do probability amplification with a small number of repetitions, whereas for general PP problems you can't.

share|improve this answer

Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively.

Let $M$ be a bounded error probabilistic polynomial-time algorithm for a language $L$ that answers correctly with probability at least $p\geq\frac{1}{2}+\delta$. Let $x$ be the input and $n$ the size of the input.

What distinguishes an arbitrary $\mathsf{PP}$ algorithm from a $\mathsf{BPP}$ algorithm is the positive gap between the probability of accepting $x\in L$ and the probability of accepting $x\notin L$. The essential thing about $\mathsf{BPP}$ is that the gap is at least $n^{-O(1)}$. I will try to explain why this distinction is significant and allows us to consider $\mathsf{BPP}$ to be considered efficient algorithms (even conjectured to be equal to $\mathsf{P}$) whereas $\mathsf{PP}$ is considered inefficient (actually $\mathsf{PP}$ contains $\mathsf{NP}$). All of this comes from this gap.

Let's start by looking at $\mathsf{PP}$ more carefully.

Note that if an algorithm uses at most $r(n)$ random bits during its execution and the error probability is smaller than $2^{-r(n)}$ then error probability is actually $0$, there cannot be any chose of random bits that will make the algorithm answer incorrectly.

Furthermore, an algorithm with running time $t(n)$ cannot use more than $t(n)$ random bits, so if a probabilistic algorithm's error with worst-case running-time $t(n)$ is better than

With a similar argument we can show that the case where the difference between the probability of accepting an $x\in L$ and the probability of accepting an $x\notin L$ is too small is similar to the case where we don't have almost no difference as in $\mathsf{PP}$ case.

Let's now move towards $\mathsf{BPP}$.

In probabilistic algorithms, we can boost the probability for correctly answering. Let's say we want to boost the correctness probability to $1-\epsilon$ for say error probability $\epsilon=2^{-n}$ (exponentially small error).

The idea is simple: run $M$ several times and take the majority's answer.

How many times should we to run $M$ to get the error probability to be at most $\epsilon$? $\Theta(\delta^{-1} \lg \epsilon)$ times. The proof is given at the bottom of this answer.

Now let's take into the consideration that the algorithms we are discussing need to be polynomial-time. That means that we cannot run $M$ more than polynomially many times. In other words, $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$, or more simply

$$\delta^{-1} \lg \epsilon = n^{O(1)}$$

This relation categorizes the bounded error probabilistic algorithms into classes depending on their error probability. There is no difference between the error probability $\epsilon$ being being $2^{-n}$ or a positive constant (i.e. doesn't change with $n$) or $\frac{1}{2}-n^{O(1)}$. We can get from one of these to the other ones while remaining inside polynomial time.

However if $\delta$ is too small, say $0$, $2^{-n}$, or even $n^{-\omega(1)}$ then we don't have a way of boosting the correctness probability and reducing the error probability sufficiently to get into $\mathsf{BPP}$.

The main point here is that in $\mathsf{BPP}$ we can efficiently reduce the error probability exponentially so we are almost certain about the answers and that is what makes us consider this class of algorithms as efficient algorithms. The error probability can be reduced so much that a hardware failure is more likely or even a meteor falling on the computer is more likely than making an error by the probabilistic algorithm.

That is not true for $\mathsf{PP}$, we don't know any way of reducing the error probability and we are left almost as if we are answering by throwing a coin to obtain the answer (we are not completely, the probabilities are not half and half, but it is very close to that situation).


This section gives the proof that to obtain error probability $\epsilon$ when we start with an algorithm with gap $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ we should run $M$ $\Theta(\delta^{-1} \lg \epsilon)$ times.

Let $N_k$ be the algorithm that runs $M$ for $k$ times and then answers according to the answer of majority. For simplicity, lets assume that $k$ is odd so we don't have ties.

Consider the case that $x \in L$. The case $x \notin L$ is similar. Then $$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$$ To analyze the correctness probability of $N_k$ we need to estimate the probability that majority of the $k$ runs accept.

Let $X_i$ be 1 if the $i$th run accepts and be $0$ if it rejects. Note that each run is independent from others as they use independent random bits. Thus $X_i$s are independent Boolean random variables where $$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$$

Let $Y = \Sigma_{i=1}^k X_i$. We need to estimate the probability that majority accept, i.e. the probability that $Y\geq\frac{k}{2}$.

$$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$$

How to do it? We can use Chernoff bound which tells us the concentration of probability near the expected value. For any random variable $Z$ with expected value $\mu$, we have

$$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$$

which says that the probability that $Z$ is $\alpha\mu$ far from its expected value $\mu$ is exponentially decreases as $\alpha$ increases. We will use it to bound the probability of $Y < \frac{k}{2}$.

Note that by linearity of expectation we have $$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$$

Now we can apply the Chernoff bound. We want an upper-bound on the probability of $Y< \frac{k}{2}$. The Chernoff bound will give an upper-bound on the probability of $|Y-(\frac{k}{2}+k\delta)| > k\delta$ which is sufficient. We have

$$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if we pick $\alpha$ such that $\alpha kp = k\delta$ we are done, so we pick $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$.

Therefore we have

$$Pr\{Y < \frac{k}{2} \} \leq Pr\{|Y - (\frac{k}{2}+k\delta)| > k\delta\} \leq Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if you do the calculations you will see that

$$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$$

we have

$$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$$

We want the error to be at most $\epsilon$, so we want

$$e^{-\Theta(k\delta)} \leq \epsilon$$

or in other words

$$\Theta(\delta^{-1} \lg \epsilon) \leq k $$

One essential point here is that in the process we will use many more random bits and also the running time will increase, i.e. the worst-case running-time of $N_k$ will be roughly $k$ times the running-time of $M$.

Here the mid point of the gap was $\frac{1}{2}$. But in general this doesn't need to be the case. We can adopt a similar method for other values by taking other fractions in place of majority for accepting.

share|improve this answer

Using your notation:

$BPP =\{L : \exists $ a probabilistic polynomial-time Turing Machine $ M, $ and a costant $ 0 < c \leq 1/2$ such that $\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists $ a probabilistic polynomial-time Turing Machine $ M$ such that $\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

The difference has been pointed out by adrianN, and you can also take a look at Wikipedia PP vs BPP

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.