Пятница, 18 ноября, ауд. 106. Начало в 18:00.
Докладчик: Дмитрий Чистиков (МГУ).
Тема: Бесповторные булевы функции и задачи их тестирования.
Abstract
Булева функция называется бесповторной в базисе
![$ B $](../../../sites/default/files/tex/4652f9965889b850c85b6146c79d9411f83d9142/index.png)
, если она выразима формулой над этим базисом, в которой каждая переменная встречается не более одного раза. В докладе будут сформулированы различные критерии бесповторности и указана роль свойства бесповторности в теории формульной сложности. После этого будут сформулированы постановки задач тестирования бесповторных функций (связанных с восстановлением и точной идентификацией, или расшифровкой, неизвестной функции) и приведен обзор известных
результатов и оценок сложности в этих задачах.