Laboratory of Mathematical Logic at PDMI

Пятница, 18 ноября, ауд. 106. Начало в 18:00.

Докладчик: Дмитрий Чистиков (МГУ).

Тема: Бесповторные булевы функции и задачи их тестирования.

Abstract

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