3. Monte Carlo & Las Vegas Algorithms

Probabilistic Complexity Classes

Bounded-error Probabilistic Polynomial Time (BPP)

A language $L$ is said to be solvable in Bounded-error Probabilistic Polynomial Time (BPP) if there is some machine $M$ that is:

• Probabilistically “Sound”: $\text{if }w\notin L\text{ then Prob}(M(w)=1)\le \frac{1}{3}$
• Probabilistically “Complete”: $\text{if }w\in L\text{ then Prob}(M(w)=1)\ge \frac{2}{3}$
• Polynomial-time: $T(n)\in O(n^k)\text{ for some }k>0$

This class corresponds to Monte Carlo Algorithms, these are randomised algorithms with deterministic runtime but may return incorrect answers due to their probabilistic nature.

Always fast and probably correct.

Link to original

Zero-error Probabilistic Polynomial Time (ZPP)

A language $L$ is said to be solvable in Zero-error Probabilistic Polynomial Time (ZPP) if there is some machine $M$ that is:

• Sound: $\text{if }w\notin L\text{ then Prob}(M(w)=1)=0$
• Complete: $\text{if }w\in L\text{ then Prob}(M(w)=1)=1$
• Expected Polynomial-time: $E[T(n)]\in O(n^k)\text{ for some }k>0$

This class corresponds to Las Vegas Algorithms, these are randomised algorithms that are always sound and complete, but their runtime may vary due to their probabilistic nature.

Always correct and probably fast.

Link to original

Theorem: $ZPP\subseteq BPP$

1. Suppose that $L\in ZPP$ then there is some PTM $M$ that is sound and complete with respect to the language $L$ with an expected polynomial runtime: $E[T(n)]<c\cdot n^k\text{ for some }c,k>0$
2. Construct a new PTM $M^{\prime }$ as follows, where $K=3\cdot E[T(n)]$:
3. It is clear that $M^{\prime }$ always terminates in $O(n^k)$ steps by design.
4. We claim that this algorithm is probabilistically sound: $w\notin L\Rightarrow \text{Prob}(M^{\prime }(w)=1)\le \frac{1}{3}$
   1. Suppose that $w\notin L$
   2. Since, $M$ is sound $M^{\prime }$ will only incorrectly accept if it had to guess: $\begin{array}{rl}{M}^{\prime }(w)& =1\iff T(n)>3\cdot E[T(n)]\\ \text{Prob}(M^{\prime }(w)=0)& \le \text{Prob}(T(n)>3\cdot E[T(n)])\le \frac{1}{3}\text{ by Markov’s inequality}\\ \text{Prob}(M^{\prime }(w)=1)& \ge 1-\text{Prob}(T(n)>3\cdot E[T(n)])\ge 1-\frac{1}{3}\\ & \ge \frac{2}{3}\end{array}$
5. Hence our machine $M^{\prime }$ is a polynomial-time Monte Carlo algorithm, therefore $L\in BPP$.

Complexity Hierarchy

This is our current complexity hierarchy: