Сложности, часть 2 + рандом (4 февраля 2025)

  1. NP (nondeterministic polynomial time) - причём тут "недетерминированность"?

  2. Сведения, decision/search
    1. Размер максимальной клики (бинпоиск)
    2. Сама клика (фиксируем вершины по одной)
    3. SAT (фиксируем значения переменных по одной)
    4. Сведение: search 3-SAT → search k-INDEPENDENT (иногда то же сведение работает для search задач)

  3. Гипотезы
    1. Придумать время работы между полиномом и экспонентой (2sqrt(logn))

  4. Примеры
    1. Поиск числа, которое встречается в массиве больше половины раз: decision и search версии, RP и ZPP.
    2. k-я статистика и quick-sort (нам было сложно корректно выбрать медиану, что дал рандом? упрощение реализации)
    3. Пример алгоритма: 3-SAT (3-LIST-COLORING будет на практике) (подсказка − что выкинуть, работает на 2n из 3n подсказок)
    4. Поиск квадратичного невычета за O(log n).
    5. Проверка того, что AB = C: A(Bx) = Cx. Доказательство.

  5. Вероятностные алгоритмы: База
    1. Вероятностные алгоритмы (Probabilistic): Определение классов RP, coRP (работает на всех входах за полином, иногда ошибается)
    2. Вероятностные алгоритмы (Randomized): Определение класса ZPP. Работает всегда корректно, матожидание времение работы − полином.
    3. Отличие от детерминированных (есть подсказка = случайные биты, работает с некоторой вероятностью)
    4. Связь с недетерминированными (работает на половине подсказок)
    5. Понижение вероятности ошибки: p → pn (понижение от константы; понижение до константы)

  6. Теорема: ZPP = RP ∩ coRP
    1. Док-во: можно запустить с будильником алгоритм из ZPP, а можно запускать по очереди алгоритмы из RP и coRP

  7. random walk
    1. Решение SAT за 3n/2 (детерминированно)
    2. Решение SAT за 3n/2 (рандомизированно): что дал рандом? упрощение реализации
    3. Решение SAT за 1.334n (рандомизированно)
    4. Пример из жизни: вы в незнакомом городе, хотите найти хорошую кафешку. (а) перебор окрестности, (б) random walk, (в) repeat random walk

  8. Парадокс дней рождений и факторизация поллардом
    1. Сам парадокс. Оценка вероятностей в обе стороны.
    2. Факторизация: алгоритмы за корень, рандомизированный с gcd за корень.
    3. Факторизация: ро-эвристика Полларда для факторизации чисел.
− Перерыв −
  1. Сложность
    1. Теорема Левина: алгоритм для решения всех NP задач за околооптимальное время
    2. Класс PSPACE и вложение в NP. wiki
    3. Класс L (logn памяти). NL. Догадайтесь? wiki
    4. path(a,b) за log2n бит памяти, ham-path за полином памяти
    5. Итого: L ⊂ NL ⊂ P ⊂ NP ⊂ PSPACE ⊂ EXP. Известно, что NL ≠ PSPACE, что P ≠ EXP. Но неизвестны все одинарные включения и, например, L =? NP.