Рандомизированные алгоритмы (11 февраля 2025)

  1. Сложность
    1. Класс PSPACE: NP in PSPACE in EXP. wiki
    2. Класс L, вложение в P.
    3. ?? AC0

  2. Всё ещё сложные задачи
    1. ham-path: 3-connected 3-regular bipartite graphs
    2. 3-coloring: planar

  3. Проверка на простоту
    1. Проверка на простоту, тест Ферма, 1/2 (Кармайкал, коррейтный тест за n1/3)
    2. Проверка на простоту, тест Миллера-Рабина, 3/4 (1977)
    3. For example, to correctly determine the primality of 32-bit numbers, it is enough to test 2 7 61

  4. BPP, PP
    1. Определение (1/3 vs 2/3)
    2. Сравнение BPP с PP, вложение NP в PP.
    3. Понижение ошибки: алгоритм и доказательство
    4. Текущая цепочка вложений: P, ZPP, RP, BPP?NP, PP, PSPACE, EXP

  5. Как ещё можно применить случайные числа?
    1. Идеальное кодирование (x + random) mod M
    2. Вычисления без разглашения: пример со средней зарплатой (zero-knowledge-proofs).
    3. Приближение с рандомом: HyperLogLog
    4. [skipped] Приближение без рандома: VERTEX-COVER to ILP to LP;
    5. [skipped] 0.5-приближение к MAX-SAT (было в практике)

  6. Алгебра многочленов и Шварц-Зиппель
    1. Лемма Шварца-Зиппеля: P(x) над F, Prx[P(x) = 0] ≤ deg P / |F|; Доказательство для многочленов от нескольких переменных.
    2. Самый простой пример: матрица Татта (1947)
    3. Пример посложнее (только описание, без решения): Гамильтонов путь в неорграфе за 1.657n (2010) (будет на 3-м курсе)

  7. random shuffle
    1. Как его получить: random shuffle через цикл for (все n! перестановок с равной вероятностью)
    2. Зачем он нужен? Дерево поиска, добавление данных в случайном порядоке.

  8. k-путь за exp(k) через рандом

  9. Игра на дереве (переехало из практики; а в практику добавим AB-отсечение)
    1. Шахматы и оценка позиции
    2. AB-Отсечение

  10. Что мы ещё пройдём?