Laboratory of Mathematical Logic at PDMI

Понедельник, 5 ноября, комната 203. Начало в 11:00.

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

Тема: Функция Норберта Блюма.

Abstract

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

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