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\ge 0}RP(2^{-n^c})=NP \quad \mathcal{RP}(n^{-c})= \mathcal{RP}(\frac{1}{2})=\mathcal{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 \(\ge \frac{3}{4}\). and if \(x\notin L\) A accept in prob \(\le \frac{1}{4}\)

\[ \quad co-\mathcal{RP}=BPP(\frac{1}{2},1)\quad BPP(\alpha -n^{-c},\alpha +n^{-c})=BPP(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 (ax=bx)\le 1/2\)

Proof ▼

supose \(a_j\neq b_j\) Let \(\alpha =\sum a_ix_i,\beta =\sum b_ix_i\) when \(i\neq j\). then \(ax=\alpha +a_ix_i\), \(bx=\beta +b_ix_i\) then

\[ ax - bx = ( \alpha -\beta )+(a_i- b_i) x_i \Pr (ax - bx=0)= \Pr \left(x_i \frac{\alpha -\beta }{b_i-a_i}\right)\le 1/2 \]

Theorem

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