0. Комментарии к предыдущей лекции: tin, tout, алгоритм через tin, а не глубину

1. Алгоритмически неразрешимые задачи: Halting Problem
2. Понятие Decision и Search задач
2.1 примеры: гамильтонов путь (существование, сам путь), клики (макс размер, >= k)
2.2 Понятие языка, связь с Decision задачами

3. Определения: DTime, P, EXP
4. Полиномиальная иерархия, DTime(f) subsetneq DTime(f log^2 f)
4.1 Пруф в другой раз
4.2 Следствие: P != EXP

5. Слово в языке если хотя бы одна подсказка сработает. Класс NP. Примеры.
5.1 P subset NP subset EXP, P != EXP (скорее зря, т.к. входит в практику)
6. Класс coNP, два определения. Примеры.
7. Полиномиальное сведение, сведение по Куку, класс NP-hard, класс NP-complete.

8. BH in NPc.
9. BH → CIRCUIT-SAT → SAT → 3-SAT → k-INDEPENDENT → k-CLIQUE
9.1 BH → CIRCUIT-SAT. Доказываем с небольшими взмахами рук.
9.2 CIRCUIT-SAT → SAT не доказываем, на пракитку.
9.3 3-SAT → k-INDEPENDENT
9.4 k-INDEPENDENT → k-CLIQUE, легчайше.
10. Практические кукареки: решение сложных задач через Sat-solver
11. Классы Search задач
11.1 Сведения search к decision (бинпоиск, находим набор для SAT)
11.2 Сведения search к search (на примере 3-SAT → k-INDEPENDENT)

12. Гипотезы: P != NP, ETH, SETH.