Семинар 13. Полиномиальная вероятностная логика для рассуждения о вероятностях

В этом докладе будут рассмотрены некоторые логики, позволяющие рассуждать о вероятностях. Сначала мы рассмотрим логику, позволяющую оперировать с неравенствами между полиномами от вероятностей. Пример формулы в её языке: $2 w (p_1 \wedge p_2) \cdot w(p_2) + 3 w (p_1) > 2$, где $w$ — аналог вероятностной меры. Мы увидим, что в этом случае каждая выполнимая формула выполнима в некоторой структуре полиномиального размера от длины формулы. Отсюда можно получить разрешимость проблемы выполнимости для вышеупомянутой логики посредством алгоритма из PSPACE. Кроме того, будет рассмотрено расширение этой логики посредством добавления кванторов по вещественным числам. Здесь имеют место схожие результаты, но уже для структур экспоненциального размера от размера данной формулы.