Поиск в глубину-3 и начало сложности (21 января 2024)

1. 2-связность: продолжение
   1. Поиск мостов за O(V+E)
   2. Поиск точек сочленения за O(V+E)
   3. Сами компоненты двусвязности: снимаем со стека
   
   
2. 2-SAT
   1. Формулировка задачи
   2. Переборное решения
   3. Граф следствий. Решение за O(VE).
   4. Наблюдение через компоненты сильной связности: когда решений не существует
   5. Решение за O(V+E), корректность
   
   
3. Сложность
   1. Цель: наконец разобраться с тем, какие по сложности задачи бывают
   2. Алгоритмически не разрешимая задача (halting). Доказательство (диагонализация). Ещё пример: пуст ли язык regexp.
   3. P: поиск пути; NP: поиск гамильтонова пути
   4. Классы: DTime, P, EXP, NP (NP без формализма)
   5. Сведения на примере IS и VC; ## NP-hard; NP-complete
   6. Примеры NP-полных задач: SAT, Clique, IS, VC, SUBSETSUM, HAMPATH, 3-COLORING
   7. Формальные определения NP, coNP; Decision-задача = множество = язык; Примеры: HAMPATH, PRIME.
   
   
4. [skipped] Сложность, не вошедшее
   1. [skipped] Полиномиальная иерархия: DTIME[f] строго в DTIME[f*log²(f)] (запуск с будильником). Следствие P ≠ EXP.
   2. [skipped] Разрешимые: decision, search. Decision-задача = множество = язык.
   3. [skipped] Класс NP, примеры (k-CLIQUE & MAX-CLIQUE, BOUNDED-HALTING = BH, HAM-PATH, PRIME & coPRIME, IS-SORTED)
   4. [skipped] Классы NP-hard (NPh), NP-complete (NPc), полиномиальное сведение