Randomized

Theorem

The class RP consists of all languages L that have a polynomial-time randomized algorithm A with the following behavior:
if $x \in L,$ then A accept $x$ in prob at most $\frac{1}{2}$ . and if $x \notin L$ A always reject

\cup_{c \geq 0} R P (2^{- n^{c}}) = N P RP (n^{- c}) = RP (\frac{1}{2}) = RP (1 - 2^{- n^{c}})

Theorem

The class BPP consists of all languages L that have a polynomial-time randomized algorithm A with the following behavior:
if $x \in L,$ then A accept $x$ in prob $\geq \frac{3}{4}$ . and if $x \notin L$ A accept in prob $\leq \frac{1}{4}$

c o - RP = B P P (\frac{1}{2}, 1) B P P (α - n^{- c}, α + n^{- c}) = B P P (2^{{- n}^{c}}, 1 - 2^{{- n}^{c}})

Theorem

(random algo) Given n digits strings $a, b \in R^{n}$ and $x \in {0, 1}^{n}$ then $Pr (a x = b x) \leq 1 / 2$

Proof ▼

supose $a_{j} \neq b_{j}$ Let $α = \sum a_{i} x_{i}, β = \sum b_{i} x_{i}$ when $i \neq j$ . then $a x = α + a_{i} x_{i}$ , $b x = β + b_{i} x_{i}$ then □

a x - b x = (α - β) + (a_{i} - b_{i}) x_{i} Pr (a x - b x = 0) = Pr (x_{i} \frac{α - β}{b_{i} - a_{i}}) \leq 1 / 2

Theorem

(Adelman’s Theorem) Every $L \in B P P$ can be decided by a family ${C_{n}}_{n \in N}$ of poly-size circuts