Введение в теорию сложности (15 февраля 2017)

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