Семинары: А. А. Вороненко, Оценки размера области определения частичной булевой функции, достаточной для порождения любой линейной

СЕМИНАРЫ


Научно-исследовательский семинар кафедры дискретной математики ФИВТ МФТИ 9 декабря 2014 г., г. Москва, ул. Льва Толстого, д. 16, Яндекс, БЦ «Морозов», ауд. «7.Пятниц»

Оценки размера области определения частичной булевой функции, достаточной для порождения любой линейной А. А. Вороненко Московский государственный университет им. М. В. Ломоносова, факультет вычислительной математики и кибернетики
Аннотация: Рассматривается задача нахождения частичной булевой функции n переменных, у которой для любой линейной функции найдется $n+1$ набор в общем положении, что позволяет однозначно задать линейную функцию. Такие функции называются универсальными и существуют при $n \ge 4$. Размер необходимой области определения ограничен линейными по $n$ функциями. Их оценке и посвящен доклад.