Введение в теорию сложности (28 января 2025)

  1. Напоминание: Decision/Search, NP, coNP, Сведение, Halting.
  2. Новые определения: BH (которая NPc), CIRCUIT-SAT, сведения по Куку/полиномиальное.
  3. NPc задачи
  4. Сведения BH → CIRCUIT-SAT → SAT → 3-SAT → k-INDEPENDENT → k-CLIQUE (получили набор NP-полных задач)
    1. BH
    2. Circuit-SAT
    3. КНФ и ДНФ (почему-то не было на дискретке)
    4. SAT, 3-SAT
    5. k-INDEPENDENT
− Перерыв −
  1. Сведение: search → decision (бинпоиск и SAT)
  2. Сведение: search 3-SAT → search k-INDEPENDENT
  3. Сведения L → SAT и применение SAT-solver (а также к ILP, и ILP-solver).
  4. Гипотезы: P != NP, ETH, SETH (при этом есть 3-SAT за 1.3n и очевидный SAT за 2n)
− Перерыв −
  1. Алгоритмы Полларда
    1. Идея с gcd, алгоритм за O(d), обоснование d ≤ n1/2
    2. Парадокс дней рождений: у каких-то d1/2 чисел совпадут остатки
    3. Псевдорандом: f(x) = x2 + 1, алгоритм поиска делителя за d1/2 = O(n1/4).