Среда 07.10. Анастасия Софронова: "Нижние оценки на задачи поиска для (1, +k)-ветвящихся программ"
PDMI seminars
Тема: Нижние оценки на задачи поиска для (1, +k)-ветвящихся программ
Место: Zoom (обратите внимание на нестандартный день семинара!)
Время: 07.10.2020, 18:00
Докладчик: Анастасия Софронова
Abstract:
В докладе мы докажем нижнюю оценку на задачу поиска невыполненного клоза для ветвящихся программ с ограниченным числом повторений переменных; а именно, нижнюю оценку $2^\Omega(n/k^2)$ для семейства формул $f_n$ размера poly(n) и $k = O(\log n/ \log \log n)$, где k — число повторений переменных. Семейство формул представляет собой некоторую модификацию невыполнимых формул, кодирующих существование линейного порядка без минимума на множестве из n элементов.
Ссылка на Zoom будет отправлена на рассылку семинара за пару часов до начала доклада.
Dmitry M. Itsykson
--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/00000000000031e7fe05b0c35f18%40google.com.