#матлог #не_мехмат #ВШЭ

57-е заседание Математического семинара ФКН состоится 24 апреля в 18:10.

На семинаре выступит Станислав Сперанский с докладом "Элементарные теорий классов вероятностных пространств и их сложность".

Доклад будет посвящён элементарным теориям различных классов вероятностных пространств (конечных, дискретных, безатомных) и сопутствующим алгоритмическим проблемам. Более того, будут рассмотрены «слабые» пространства, в которых меры подразумеваются конечно-аддитивными, но не обязательно счётно-аддитивными: они используются в семантике многих вероятностных логических систем, возникающих в теоретической информатике. Стоит отметить, что хотя основное внимание будет сосредоточено на языках, близких к традиционно изучаемым элементарным языкам полей и решёток, у практически всех сопутствующих результатов имеются естественные аналоги для «первопорядковых логик вероятности», которые возникли в работах Дж. Хальперна и чьи варианты продолжают активно изучаться.

Рассказ будет ориентирован на широкую математическую аудиторию. В частности, понятия элементарного языка и теории будут пояснены на примерах, связанных с алгоритмическими проблемами над кольцами и полями, включая 10-ую проблему Гильберта. Кроме того, будет дано определение сводимости посредством вычислимых функций, используемой для сравнения различных теорий по сложности, и приведены примеры проблем, соответствующих некоторым часто возникающим сложностным классам, или «степеням (алгоритмической) неразрешимости».

Семинар пройдет по адресу Покровский бульвар 11, аудитория R306.

Информация о семинаре и аннотация предстоящего доклада: https://cs.hse.ru/seminatfkn/

Регистрация: https://cs.hse.ru/big-data/polls/788384338.html