Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Нижние оценки для SAT. Схемная сложность
Основы вычислимости и теории сложности

Что: Лекция
Когда: Среда, 28 ноября 2012, 18:30–19:50
Где: ПОМИ РАН

Описание

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