On the complexity of first-order logics of probability
Stanislav Olegovich Speranski, Alexander Vitalevich Grefenshtein · Известия Российской академии наук Серия математическая · 2026
The article is concerned with Halpern's first-order logics of probability, which we denote by $\mathscr{L}_1$ and $\mathscr{L}_2$ - the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [1] of the complexity lower bound results for $\mathscr{L}_1$ and $\mathscr{L}_2$ rely heavily on using polynomials. We shall obtain the same lower bounds for small fragments of $\mathscr{L}_1$ and $\mathscr{L}_2$ in which neither addition nor multiplication is allowed. Further, it will be studied what happens if we exclude field variables, and hence quantifiers over reals; the upper bound proofs here will utilize suitable analogues of the (downward) Löwenheim-Skolem theorem.