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

  1. Цель: наконец разобраться с тем, какие по сложности задачи бывают
  2. Алгоритмически не разрешимая задача (halting). Доказательство (диагонализация). Ещё пример: пуст ли язык regexp.
  3. Разрешимые: decision, search. Decision-задача = множество = язык.
  4. Классы: DTime, P, EXP
  5. Полиномиальная иерархия: DTIME[f] строго в DTIME[f*log2(f)] (запуск с будильником). Следствие P ≠ EXP.
  6. Класс NP, примеры (k-CLIQUE & MAX-CLIQUE, BOUNDED-HALTING = BH, HAM-PATH, PRIME & coPRIME, IS-SORTED)
  7. Классы NP-hard (NPh), NP-complete (NPc), полиномиальное сведение
− Перерыв −
  1. Цель: найти хотя бы одну NP-полную задачу и построить ордерево сведений многих задач.
  2. Th: BH ∈ NP-complete
  3. Сведения BH → CIRCUIT-SAT → SAT → 3-SAT → k-INDEPENDENT → k-CLIQUE (получили набор NP-полных задач)
  4. Сведения L → SAT и применение SAT-solver
  5. Сведение: search → decision (бинпоиск и SAT)
  6. Сведение: search 3-SAT → search k-INDEPENDENT
  7. Гипотезы: P != NP, ETH, SETH (при этом есть 3-SAT за 1.3n и очевидный SAT за 2n)