Город: Язык: Русский English
Что: Лекция
Когда: Среда, 05 ноября 2014, 18:30–19:50
Где: ПОМИ РАН

Описание

Оракульное определение полиномиальной иерархии. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Существование функций большой схемной сложности. Теорема Карпа-Липтона. Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана).