#дневниклекций
На прошедших двух лекциях 8 и 22 октября изучали полиномиальную иерархию и начали полиномиальную память. Немного подробнее про то, что было:
- Задача о проверке значения кликового числа. Почему она NP-трудна, но скорее всего не в NP. Представление её как разности двух языков из NP. Преобразование в формулу с двумя кванторами. Класс DP.
- Другие примеры возникновения формулы с двумя или тремя кванторами: минимизация формулы, кликовая раскраска, в том числе наследственная, обобщённая рамсеевость, размерность Вапника-Червоненкиса
- Определение классов полиномиальной иерархии, вложения одних в другие.
- Если P=NP, то P=PH.
- Три условия коллапсирования полиномиальной иерархии, их эквивалентность.
- Существование полных задач на уровнях иерархии. Задачи Sigma_k-SAT и Pi_k-SAT, эквивалентность друг другу их полноты в соответствующих классах для каждого k. Доказательство полноты для случая, когда последний квантор - квантор существования. Эквивалентность существования полной задачи во всей иерархии и её коллапсирования.
- Альтернирующие машины и их связь с полиномиальной иерархией.
- Игровой взгляд на задачи из PH как множества выигрышных позиций в играх с фиксированным числом ходов.
- Измерение памяти, используемой машиной. Модель с неизменяемым входом и рабочей лентой. Классы DSPACE(s(n)) и NSPACE(s(n)).
- Соотношения временных и пространственных классов: L вложено в P, PSPACE вложено в EXP, NL вложено в P (доказательство через конфигурационный граф). Формулировка теоремы Сэвича, следствие: PSPACE=NPSPACE.

Сегодня докажем теорему Сэвича и поговорим о PSPACE-полных задачах. Если останется время, посмотрим на задачи из класса L.