Введение в теорию сложности, часть 2 (5 февраля 2024)

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

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

  3. Гипотезы
    1. Придумать время работы между полиномом и экспонентой (2sqrt(logn))
    2. Гипотезы: P ≠ NP, ETH, SETH (при этом есть 3-SAT за 1.3n и очевидный SAT за 2n)
    3. SETH ⇒ ETH ⇒ P ≠ NP (рассказать, как из ETH следует P ≠ NP, и почему для SETH ⇒ ETH сложнее, что такое спарсификация)
− Перерыв −
  1. Вероятностные алгоритмы: База
    1. Вероятностные алгоритмы (Probabilistic): Определение классов RP, coRP (работает на всех входах за полином, иногда ошибается)
    2. Вероятностные алгоритмы (Randomized): Определение класса ZPP. Работает всегда корректно, матожидание времение работы − полином.
    3. Отличие от детерминированных (есть подсказка = случайные биты, работает с некоторой вероятностью)
    4. Связь с недетерминированными (работает на половине подсказок)
    5. Понижение вероятности ошибки: p → pn

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

  3. Теорема: ZPP = RP ∩ coRP (можно запустить с будильником алгоритм из ZPP, а можно запускать по очереди алгоритмы из RP и coRP)

  4. Парадокс дней рождений и факторизация
    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.