Laboratory of Mathematical Logic at PDMI

Пятница, 28 декабря, комната 106. Начало в 16:00.

Докладчик: С. Николенко.

Тема: О некоторых нижних оценках на размеры булевых схем.

Abstract

Доклад, в частности, по статье A. Hiltgen.

Булева схема - это ориентированный граф без циклов, в вершинах (гейтах) которого расположены булевы операции.

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

Также будет дан обзор связанных с этим открытых вопросов, путей их решения и основных трудностей на этих путях - с приглашением к дискуссии.