Математический семинар ФКН "Элементарные теорий классов вероятностных пространств и их сложность"

24 апреля 2026 в 18:10

Докладчик: Станислав Сперанский, МИАН НИУ ВШЭ

Тема: Элементарные теорий классов вероятностных пространств и их сложность

Аннотация: 

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

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

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