Pseudorandomness Learning Notes

Pseudorandomness learning notes.

The Power of Randomness

Some Kinds of Complexity Classes

Monte Carlo:

Randomized Polynomial Time: $\text{RP}$ is a class of languages $L$: $\exists$ a probabilistic polynomial time algorithm $A$, s.t.:

$x\in L\Rightarrow \Pr[A(x)\text{ accepts}]\ge 1/2\\ x\notin L\Rightarrow \Pr[A(x)\text{ accepts}]=0$

Bounded-error Probabilistic Polynomial Time: $\text{BPP}$ is a class of languages $L$: $\exists$ a probabilistic polynomial time algorithm $A$, s.t.:

$x\in L\Rightarrow \Pr[A(x)\text{ accepts}]\ge 2/3\\ x\notin L\Rightarrow \Pr[A(x)\text{ accepts}]\le 1/3$

Las Vegas:

Zero-error Prbabilistic Polynomial Time: $\text{ZPP}$ is a class of languages $L$: $\exists$ a always correct probabilistic algorithm $A$ runs in expected polynomial time.

Problem 2.3 (Zero error versus 1-sided error): Prove that $\text{ZPP} = \text{RP} ∩ \text{co-RP}$.

Proof: First we prove that $\text{RP} ∩ \text{co-RP}\subset \text{ZPP}$.

Let $L$ be a language in $\text{RP} ∩ \text{co-RP}$.

$L\in \text{RP}$ tells us that there exists a probabilistic polynomial time algorithm $A$, s.t.:

$x\in L\Rightarrow \Pr[A(x)\text{ accepts}]\ge 1/2\\ x\notin L\Rightarrow \Pr[A(x)\text{ accepts}]0$

Similarly, there exists a probabilistic polynomial time algorithm $B$, s.t.:

$x\in L\Rightarrow \Pr[A(x)\text{ accepts}]=1\\ x\notin L\Rightarrow \Pr[A(x)\text{ accepts}]\le 1/2$

We design a algorithm $C$ that $\forall x\in \{0,1\}^*,C(x)\text{ accepts}\iff B(x)\text{ accepts},C(x)\text{ rejects}\iff A(x)\text{ rejects}$.

Obviously, $C$ is always correct. and runs in polynomial time. Therefore $L\in \text{ZPP}$. Thus we have $\text{RP} ∩ \text{co-RP}\subset \text{ZPP}$.

Second we prove that $\text{ZPP} \subset \text{RP} ∩ \text{co-RP}$.

Let $L$ be a language in $\text{ZPP}$, thus there exists a always correct probabilistic algorithm $A$ runs in expected polynomial time.

Let $\mathbb E(t)$ be the expected running time of $A$. We run $A$ in at most $2\mathbb E(t)$ time. If $A(x)$ does not stop in $2\mathbb E(t)$ time, we let $A$ directly reject $x$.

Obviously, $\Pr[A(x)\text{ rejects}]=0\,(x\notin L)$. And by using Markov’s inequality, we have:

$\forall x\in L, \Pr[A(x)\text{ accepts}]=1-\Pr[A(x)\text{ rejects}]=1-\Pr[t>2\mathbb E(t)]\ge 1-1/2=1/2$

Therefore $L\in \text{RP}$. Similarly, $L\in \text{co-RP}$. Thus we have $\text{ZPP} \subset \text{RP} ∩ \text{co-RP}$.

The above then implies $\text{ZPP}=\text{RP} ∩ \text{co-RP}$, as desired.

$\Box$

Open Problem: Are any of inclusions $text{P}\subset \text{ZPP}\subset \text{RP} \subset \text{BPP}$ proper?