RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар С. Л. Кузнецова и С. О. Сперанского "Неклассические логики"
14 декабря 2022 г. 18:00, г. Москва, МИАН, комн. 313 (ул. Губкина, 8) + online


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

Владимир Карпов



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


© МИАН, 2024