On the complexity of first-order logics of probability

This article is concerned with Halpern’s first-order logics of probability, which we denote by L1 and L2: 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 the complexity lower bound results for L1 and L2 given in [1] relied heavily on using polynomials. We shall obtain the same lower bounds for small fragments of L1 and L2 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) Lowenheim–Skolem theorem. ¨