RUS  ENG
Полная версия
ВИДЕОТЕКА

Научная сессия МИАН, посвященная подведению итогов 2024 года
20 ноября 2024 г. 11:35, г. Москва, МИАН, конференц-зал 9 этаж + online


Элементарные теории классов вероятностных пространств

С. О. Сперанский


https://vk.com/video-222947497_456239049
https://youtu.be/b_BLtuTeK1Y

Аннотация: В доказательствах многих сложностных результатов, связанных с кванторными вероятностными логическими системами, существенно используется операция умножения вероятностей. Возникает естественный вопрос о том, что происходит при отсутствии операции умножения. В качестве основного примера можно рассмотреть следующий результат: если класс вероятностных пространств содержит все дискретные пространства, то его односортная элементарная теория (в языке с кванторами по событиям) имеет как минимум ту же сложность, что и полная арифметика второго порядка. В [1] получено усиление этого результата: вышеупомянутая оценка сложности остаётся верной, если вместо равенств и неравенств между полиномами от вероятностей мы будем использовать лишь равенства между вероятностями с постоянными натуральными коэффициентами. Также получены аналогичные результаты для обогащений известных вероятностных логик Хальперна–Фейгина–Мегиддо (без кванторов либо с кванторами по вещественным числам) посредством добавления кванторов по пропозициональным формулам.
В работе [2] построен перевод из двухсортного элементарного языка вероятностных пространств (с кванторами по событиям и кванторами по вещественным числам) в язык арифметики второго порядка, где каждое пространство определённым образом сводится к своей атомарной части. С помощью этого перевода доказано, что теория практически любого разумного ‒ в некотором смысле «аналитического» ‒ класса пространств не сложнее, чем полная арифметика второго порядка; при этом теория безатомных пространств оказывается полной и алгоритмически разрешимой.

Список литературы
  1. Stanislav O. Speranski, “Sharpening complexity results in quantified probability logic”, Log. J. IGPL, 2024, jzae114, 1–21  crossref
  2. Stanislav O. Speranski, “An ‘elementary’ perspective on reasoning about probability spaces”, Log. J. IGPL, 2024, jzae042, 1–23  mathnet  crossref  isi


Статьи по теме:


© МИАН, 2024