#### Теорема

Если существует [односторонняя перестановка](/nodes/248), то существует и [генератор псевдослучайных чисел](/nodes/276).

#### Доказательство

Проводится в три этапа:

1.  Односторонняя перестановка $\implies$ односторонняя перестановка с [трудным битом](/nodes/278):
$g(x, y) = (f(x), y)$
$\beta(x, y) = x \odot y = \oplus_{i = 1}^{n} x_i y_i$
2.  Односторонняя перестановка с трудным битом $\implies$ Генератор $n \rightarrow n + 1$
3.  Генератор $n \rightarrow n + 1$ $\implies$ Генератор $n \rightarrow p(n)$

Идея последнего шага 
$x \mapsto g(x)h(x) \mapsto g(g(x))h(g(x))h(x) \mapsto g(g(g(x)))h(g(g(x)))h(g(x))h(x) \mapsto \ldots$
***
#### Лемма 2
$\beta(x)$ - трудный бит для $f(x) \Leftrightarrow x \mapsto f(x)\beta(x)$ - генератор.

####[Доказательство](http://knowen.org/nodes/293)

Сперва построим генератор псевдослучайных чисел, отображающий $n$ битов в $p(n)$, имея генератор псевдослучайных чисел $(n \mapsto n + 1)$. 

По генератору $G(x) = g(x)h(x)$ построим $G'(x) = h(x)h(g(x))h(g(g(x)))\ldots$

#### Утверждение 
Если $G(x)$ - генератор псевдослучайных чисел, то $G'(x)$ - генератор псевдослучайных чисел.

#### [Доказательство](http://knowen.org/nodes/294)

Осталось по односторонней перестановке построить одностороннюю перестановку с трудным битом. Но сперва поговорим немного о кодах Адамара.


#### Теорема (Голдрайх-Левин) 
Если $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^n$ - односторонняя перестановка, то $g: \{0, 1\}^{2n} \rightarrow \{0, 1\}^{2n}$, $g(x, y) = (f(x), y)$ - тоже односторонняя перестановка, а $h(x, y) = x \odot y$ - трудный бит для $g$.

#### Теорема(О кодах Адамара или о списочном декодировании) 
Пусть $h_x(y) = x \odot y$ - код Адамара слова $x \in \{0, 1\}^n$. Пусть $\bar{h}(y)$ - такая функция, что доля $y$ удовлетоворяющих $\bar{h}(y) = h_x(y)$ больше либо равна $\frac{1}{2}$. Тогда существует вероятностный алгоритм, работающий $poly(\frac{n}{\varepsilon})$, имеющий произвольный доступ к $\bar{h}$, выдающий список слов длины $n$, с вероятностью $\ge \frac{1}{2}$ содержит $x$.

Почему это называется декодированием списка? Вообще кодирование нужно для исправления ошибок. Код Адамара - длинный код. Точного полиномиального алгоритма декодирования не существует. $h$ - код, $\bar{h}$ - испорченный код. 

 
#### Теорема 
Из теоремы о списочном декодировании выводится теорема Голдрайха-Левина.

#### [Доказательство](http://knowen.org/nodes/296)


#### Теорема (ЗБЧ для попарно независимых случайных величин) 
Пусть $\xi_1, \ldots, \xi_N$ - попарно независимые одинакого распределенные, бернулиевские случайные величины. $E\xi_i = \frac{1}{2} - \varepsilon$. Тогда $$Pr\{\xi_1 + \ldots \xi_N \ge \frac{1}{2}N\} \le \frac{1}{\varepsilon^2}\frac{1}{N}$$

#### [Доказательство ЗБЧ](http://knowen.org/nodes/297)
 

#### [Доказательство теоремы о списочном декодировании](http://knowen.org/nodes/298)