On the complexity of first-order logics of probability
Abstract
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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Logic
Reasoning
and Knowledge
Computability
AI Algorithms
Publication details
- Journal / source
- Известия Российской академии наук Серия математическая
- Publisher
- Steklov Mathematical Institute
- Volume
- 90
- Issue
- 4
- Pages
- 105–126
- Publication date
- 1 January 2026
- Language
- EN