Дневник лекций 2006/2007 года

8-Nov-2006

Замкнутость классов полиномиальной иерархии относительно
полиномиальной сводимости.
Полные проблемы в классах полиномиальной иерархии.

Класс
PSPACE и включение полиномиальной иерархии в PSPACE.
Полиномиальные игры. Включение класса языков, задаваемых
полиномиальными играми в класс PSPACE.

15-Nov-2006

Обратное включение.

PSPACE-полнота проблемы выяснения истинности квантифицированных
булевых формул.

PSPACE-полнота проблемы универсальности регулярного выражения.

22-Nov-2006

Класс #P, полнота задачи вычисления перманента в этом классе.

29-Nov-2006

Схемная сложность, классы n.u.P и P/poly, их совпадение.
Сверхполиномиальные нижние оценки схемной сложности
NP-полных языков и схлопывание полиномиальной иерархии.
Вероятностные полиномиальные алгоритмы, класс BPP,
уменьшение вероятности
ошибки.

6-Dec-2006

Алгоритм Миллера-Рабина
распознавания простоты чисел.
Включение класса BPP в P/poly.
Включение класса BPP во второй уровень полиномиальной иерархии.

13-Dec-2006

Интерактивное доказательство неизоморфности графов.
Включение класса IP в класс PSPACE.