Home

Понедельник 16 мая, 14-00, ауд. 203

Понедельник, 16 мая, ауд. 203. Начало в 14: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, теорема об иерархии по времени для недетерминированных вычислений, вычисления с неравномерной подсказкой.