Laboratory of Mathematical Logic at PDMI

Четверг, 1 ноября, комната 203. Начало в 15:00.

Докладчик: А. С. Куликов.

Тема: Нижние оценки для булевых схем.

Abstract

Булева схема - это ориентированный граф без циклов, каждая вершина которого вычисляет булеву операцию над битами, приходящими по входящим ребрам и выдает результат на исходящие.

Хотя из мощностных соображений почти очевидно, что совсем не каждую булеву функцию можно вычислить при помощи булевой схемы полиномиального размера, наилучшая нижняя оценка для конкретной функции является линейной. В докладе будет доказано несколько (классических) оценок.