Abstract

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of Fagin et al. (A logic for reasoning about probabilities, Inform Comput, 1990; 87:78–128). One of these, denoted by ${\textsf{QPL}}^{\textrm{e}}$, is obtained by adding quantifiers over arbitrary events, and the other, denoted by $\underline{{\textsf{QPL}}}^{\textrm{e}}$, uses quantifiers over propositional formulas—or equivalently, over events expressible by such formulas. The earlier proofs of the complexity lower bound results for ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ relied heavily on multiplication, and therefore on the polynomiality of the basic parts. We shall obtain the same lower bounds for natural fragments of ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ in which only linear combinations of a very special form are allowed. Also, it will be studied what happens if we add quantifiers over reals.