====== Algorytmy probabilistyczne - Lista 2. ======

===== Zadanie 1 =====

  * $ZPP \subseteq RP\cap coRP$ \\ Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. \\ $\Pr(t \geq a) \leq \frac{\textrm{E}(t)}{a}. => \Pr(t \geq 2E(t)) \leq \frac{1}{2}.$
  * $RP\cap coRP \subseteq ZPP$ \\ Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B. \\ Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step. \\ $P(X = k) = (1-\frac 1 2)^{k-1}\frac 1 2 = 2^{-k}$ ($X$ - liczba rund, rozklad geometryczny) \\ $E(X) = 2$\\ $E(t) = t_1E(X) = \mathrm{poly}$

===== Zadanie 2 =====
===== Zadanie 3 =====
===== Zadanie 4 =====
===== Zadanie 5 =====
===== Zadanie 6 =====