{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:04:32Z","timestamp":1753877072391,"version":"3.41.2"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T00:00:00Z","timestamp":1728604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,5,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We shall be concerned with two natural expansions of the quantifier-free \u2018polynomial\u2019 probability logic of Fagin et\u00a0al. (A logic for reasoning about probabilities, Inform Comput, 1990; 87:78\u2013128). One of these, denoted by ${\\textsf{QPL}}^{\\mathrm{e}}$, is obtained by adding quantifiers over arbitrary events, and the other, denoted by $\\underline{{\\textsf{QPL}}}^{\\mathrm{e}}$, uses quantifiers over propositional formulas\u2014or equivalently, over events expressible by such formulas. The earlier proofs of the complexity lower bound results for ${\\textsf{QPL}}^{\\mathrm{e}}$ and $\\underline{{\\textsf{QPL}}}^{\\mathrm{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}}^{\\mathrm{e}}$ and $\\underline{{\\textsf{QPL}}}^{\\mathrm{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.<\/jats:p>","DOI":"10.1093\/jigpal\/jzae114","type":"journal-article","created":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T06:44:56Z","timestamp":1728629096000},"source":"Crossref","is-referenced-by-count":3,"title":["Sharpening complexity results in quantified probability logic"],"prefix":"10.1093","volume":"33","author":[{"given":"Stanislav O","family":"Speranski","sequence":"first","affiliation":[{"name":"Steklov Mathematical Institute of Russian Academy of Sciences , Moscow,","place":["Russia"]}]}],"member":"286","published-online":{"date-parts":[[2024,10,11]]},"reference":[{"issue":"1","key":"2025052605514181300_ref1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1049","article-title":"Decidability and expressiveness for first-order logics of probability","volume":"112","author":"Abadi","year":"1994","journal-title":"Inform Comput"},{"issue":"4","key":"2025052605514181300_ref2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1070\/RM1965v020n04ABEH001188","article-title":"Elementary theories","volume":"20","author":"Ershov","year":"1965","journal-title":"Russian Math Surveys"},{"issue":"1\u20132","key":"2025052605514181300_ref3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0890-5401(90)90060-U","article-title":"A logic for reasoning about probabilities","volume":"87","author":"Fagin","year":"1990","journal-title":"Inform Comput"},{"issue":"2","key":"2025052605514181300_ref4","doi-asserted-by":"publisher","first-page":"637","DOI":"10.2307\/2274706","article-title":"Presburger arithmetic with unary predicates is $\\varPi _1^1$ complete","volume":"56","author":"Halpern","year":"1991","journal-title":"J Symbol Logic"},{"issue":"3","key":"2025052605514181300_ref5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0003-4843(78)90022-0","article-title":"Probability logic","volume":"14","author":"Hoover","year":"1978","journal-title":"Annal of Math Logic"},{"issue":"9","key":"2025052605514181300_ref6","doi-asserted-by":"publisher","first-page":"103339","DOI":"10.1016\/j.apal.2023.103339","article-title":"Probing the quantitative\u2013qualitative divide in probabilistic reasoning","volume":"175","author":"Ibeling","year":"2024","journal-title":"Annal Pure Appl Logic"},{"key":"2025052605514181300_ref7","first-page":"509","article-title":"Probability quantifiers","volume-title":"Model-Theoretic Logics","author":"Keisler","year":"1985"},{"key":"2025052605514181300_ref8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-030-52954-3_5","article-title":"Some new probability operators","volume-title":"Probabilistic Extensions of Various Logical Systems","author":"Markovi\u0107","year":"2020"},{"volume-title":"Elementary Induction on Abstract Structures","year":"1974","author":"Moschovakis","key":"2025052605514181300_ref9"},{"key":"2025052605514181300_ref10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-47012-2","volume-title":"Probability Logics","author":"Ognjanovi\u0107","year":"2016"},{"key":"2025052605514181300_ref11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-77684-0_17","article-title":"A probabilistic logic with polynomial weight formulas","volume-title":"Foundations of Information and Knowledge Systems 2008, LNCS 4932","author":"Perovi\u0107","year":"2008"},{"issue":"2","key":"2025052605514181300_ref12","doi-asserted-by":"publisher","first-page":"98","DOI":"10.2307\/2266510","article-title":"Definability and decision problems in arithmetic","volume":"14","author":"Robinson","year":"1949","journal-title":"J Symbol Logic"},{"volume-title":"Theory of Recursive Functions and Effective Computability","year":"1967","author":"Rogers Jr","key":"2025052605514181300_ref13"},{"issue":"12","key":"2025052605514181300_ref14","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1016\/j.apal.2012.04.003","article-title":"Some new results on decidability for elementary algebra and geometry","volume":"163","author":"Solovay","year":"2012","journal-title":"Annal Pure Appl Logic"},{"issue":"4","key":"2025052605514181300_ref15","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10469-011-9148-3","article-title":"Quantification over propositional formulas in probability logic: Decidability issues","volume":"50","author":"Speranski","year":"2011","journal-title":"Algebra Logic"},{"issue":"5","key":"2025052605514181300_ref16","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1093\/logcom\/exs041","article-title":"Complexity for probability logic with quantifiers over propositions","volume":"23","author":"Speranski","year":"2013","journal-title":"J Logic Comput"},{"issue":"5\u20136","key":"2025052605514181300_ref17","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00153-013-0328-9","article-title":"A note on definability in fragments of arithmetic with free unary predicates","volume":"52","author":"Speranski","year":"2013","journal-title":"Arch Math Logic"},{"issue":"2","key":"2025052605514181300_ref18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.3233\/COM-150036","article-title":"Some new results in monadic second-order arithmetic","volume":"4","author":"Speranski","year":"2015","journal-title":"Computability"},{"issue":"8","key":"2025052605514181300_ref19","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1017\/S0960129516000189","article-title":"Quantifying over events in probability logic: An introduction","volume":"27","author":"Speranski","year":"2017","journal-title":"Math Structures Comput Sci"},{"issue":"6","key":"2025052605514181300_ref20","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.4213\/im9340e","article-title":"On the coprimeness relation from the viewpoint of monadic second-order logic","volume":"86","author":"Speranski","year":"2022","journal-title":"Izvestiya: Mathematics"},{"key":"2025052605514181300_ref21","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzae042","article-title":"An \u2018elementary\u2019 perspective on reasoning about probability spaces","author":"Speranski","year":"2024","journal-title":"Log J IGPL"},{"key":"2025052605514181300_ref22","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski","year":"1951"},{"volume-title":"Undecidable Theories","year":"1953","author":"Tarski","key":"2025052605514181300_ref23"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/33\/3\/jzae114\/59715443\/jzae114.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/33\/3\/jzae114\/59715443\/jzae114.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T09:51:51Z","timestamp":1748253111000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/doi\/10.1093\/jigpal\/jzae114\/7815949"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,11]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5,23]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzae114","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"type":"print","value":"1367-0751"},{"type":"electronic","value":"1368-9894"}],"subject":[],"published-other":{"date-parts":[[2025,6]]},"published":{"date-parts":[[2024,10,11]]},"article-number":"jzae114"}}