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

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