Mathematical Logic and Discrete Mathematics at PDMI

Четверг, 8 октября, Zoom. Начало в 14:00.

Докладчик: А.В. Смаль (ПОМИ).

Тема: Универсальные формулы Де Моргана и коммуникационные протоколы.

Abstract

Будем называть формулу Де Моргана F(x_1,x_2,...,x_n) универсальной для некоторого класса функций С, если для любой функции f(y_1,y_2,...,y_m) из C существует подставновка s, сопоставляющая каждой переменной x_i некоторую переменную y_i, её отрицание или константу так, что F|s(y_1,y_2,...,y_m) вычисляет f.

Рассмотрим класс DMDepth(d) всех функций, которые вычисляются формулами Де Моргана глубины не более d. Какова наименьшая глубина D такая, что есть универсальная формула глубины D для DMDepth(d)?
Нетрудно заметить, что D лежит между d и 2d. Было бы естественно предположить, что D = 2d. Потехин показал, что есть универсальная формула глубины 5 для DMDepth(3). Это естественным образом обобщаяется: для класса функций, вычисляемых формулами глубины d, существует универсальная форму глубины D = 5/3d.

На докладе будер рассказано про улучшение этой оценки до D = 8/5d, про связь с универсальными коммуникационными протоколами и про сложности доказательства нижней оценки.