Понедельник, 16 мая, ауд. 203. Начало в 13:00.
Тема: Теорема Вильямса: $NEXP \not \subseteq ACC_0$ (часть I).
Abstract
Доклад посвящен недавнему результату Раена Вильямса о новой нижней оценке на схемную сложность. В докладе будет доказано, что в классе NEXP есть язык, который нельзя решить с помощью полиномиального размера схем из функциональных элементов, которые имеют неограниченную входную степень и константную глубину. В качестве функциональных элементах в таких схемах можно использовать конъюнкцию, дизъюнкцию, отрицание и $MOD_m$ для всех натуральных $m$. Такие схемы называют $ACC_0$-схемами, а $ACC_0$ - это класс языков, который решается такими схемами.
Доказательство разбивается на две независимые части.
Сначала показывается, что для $ACC_0$-схем ограниченной глубины есть алгоритм, решающий задачу выполнимости схемы быстрее за время $2^{n-n^\delta}$, а затем из существования такого алгоритма выводится нижняя оценка. На первом заседании семинара будет рассказан именно вывод нижней оценки из существования алгоритма. А на втором заседании семинара будет приведен алгоритм для задачи выполнимости $ACC_0$-схемы, который работает быстрее, чем полный перебор.
Для понимания доказательств из первой части доклада полезно иметь представления о таких понятиях как: интерактивные протоколы, игры Мерлина-Артура, классы сложности PSPACE, MA, теорема об иерархии по времени для недетерминированных вычислений, вычисления с неравномерной подсказкой.
