Laboratory of Mathematical Logic at PDMI

Пятница, 4 мая, 402. Начало в 12:00.

Докладчик: Людмила Глинских.

Тема: Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.

Abstract

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

Мы рассмотрим доказательство экспоненциальной нижней оценки для недетерминированных семантических 3-арных одноразовых ветвящихся программ — в таких программах каждой вершине диаграммы может соответствовать 3 различных значения.

Доклад по одноимённой работе Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi.