Оценки сложности для баз данных, снабженных логическими теориями

В докладе будет рассказано о приложении теории сложности булевых схем к так называемым базам данных с онтологическим доступом. На элементах такой базы данных задаются предикаты, а также некоторая логическая теория первого порядка. Запросом к такой базе данных является формула логики первого порядка, а ответом на запрос является набор элементов базы данных, удовлетворяющий этой формуле. Одним из основных вопросов в этой области является вопрос об алгоритмической сложности задачи поиска ответа на заданный запрос к базе данных. Стандартным подходом к решению этой задачи является переформулировка заданного запроса к базе данных в таком виде, чтобы поиск ответа мог быть найден исходя только из значений предикатов на элементах базы. При этом возникает вопрос о том, насколько увеличивается длина запроса при такой переформулировке. Мы расскажем о ряде верхних и нижних оценок этой величины при различных ограничениях на виды рассматриваемых логических теорий, запросов и переформулировок запросов. Эти оценки получены с использованием классических результатов из теории сложности булевых схем. Для доказательства оценок была введена новая модель вычисления булевых функций, так называемые гиперграфовые программы. Эта модель была использована как связующее звено между запросами к базам данных и булевыми схемами.