#дневниклекций
Сегодня продолжили доказательство теоремы о преобразовании односторонней перестановки в ГПСЧ, но целиком не закончили. Было следующее:
- Напоминание общей схемы доказательства: построение перестановки с трудным битом (теорема Левина-Голдрайха, g(x,y)=(f(x),y), h(x,y)=x⨀y), построение генератора n->n+1 (XOR-лемма Яо, G(x)=g(x)h(x)), построение генератора n->p(n).
- Формальное определение трудного бита и генератора. Формулировка контрапозиции: если предикат не задаёт трудный бит для перестановки, то результат его приписывания к перестановке можно отличить от случайного, и наоборот. Простое направление: если есть предсказатель трудного бита, то можно сравнить его результат с последним битом и на этом основании построить отличитель.
- Сложное направление: если есть отличитель, то можно построить и предсказатель. Предсказатель смотрит, для какого последнего бита отличитель даёт 1 и этот последний бит и возвращает. Если не даёт никогда или даёт всегда, то возвращает случайный бит. Аккуратно посчитали вероятности, чтобы показать, что предсказатель действительно успешный.
- Построение трудного бита. Коды Адамара. Отличие двух кодов ровно в половине битов (принцип случайных подсумм). Задача восстановления x как задача декодирования.
- Тривиальный случай: код известен точно (трудный бит предсказан с вероятностью 1)
- Простой случай: в коде меньше 1/4-ε ошибок (трудный бит предсказан с вероятностью 3/4+ε). Идея самокоррекции кода. Декодирование за счёт самокоррекции и его амплификация.
- Общий случай: в коде меньше 1/2-ε ошибок (трудный бит предсказан с вероятностью 1/2+ε). Идея декодирования списком. Основные вехи доказательства: самокоррекция с учётом неизвестных настоящих значений, амплификация за счёт попарно независимых запусков, построение семейства попарно независимых случайных строк из логарифмического числа истинно случайных, полный перебор значений кода на этих истинно случайных и построение списка возможных декодированных строк.

В следующий раз изучим последний пункт более подробно, с детальными доказательствами, а потом поговорим про псевдослучайные функции.