{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:14:37Z","timestamp":1778498077191,"version":"3.51.4"},"reference-count":45,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T00:00:00Z","timestamp":1652832000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many tasks in statistical and causal inference can be construed as problems of <jats:italic>entailment<\/jats:italic> in a suitable formal language. We ask whether those problems are more difficult, from a computational perspective, for <jats:italic>causal<\/jats:italic> probabilistic languages than for pure probabilistic (or \u201cassociational\u201d) languages. Despite several senses in which causal reasoning is indeed more complex\u2014both expressively and inferentially\u2014we show that causal entailment (or satisfiability) problems can be systematically and robustly reduced to purely probabilistic problems. Thus there is no jump in computational complexity. Along the way we answer several open problems concerning the complexity of well-known probability logics, in particular demonstrating the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1755020322000211_inline1.png\"\/><jats:tex-math>\n${\\exists \\mathbb {R}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-completeness of a polynomial probability calculus, as well as a seemingly much simpler system, the logic of comparative conditional probability.<\/jats:p>","DOI":"10.1017\/s1755020322000211","type":"journal-article","created":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T08:25:52Z","timestamp":1652862352000},"page":"106-131","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":5,"title":["IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?"],"prefix":"10.1017","volume":"17","author":[{"given":"MILAN","family":"MOSS\u00c9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DULIGUR","family":"IBELING","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THOMAS","family":"ICARD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,5,18]]},"reference":[{"key":"S1755020322000211_r26","unstructured":"[26] Ibeling, D. , & Icard, T. (2021). A topological perspective on causal inference. In Ranzato, M., editor. Proceedings of the Thirty-Fifth Conference on Neural Information Processing Systems (NeurIPS). Vancouver: Curran Associates, Inc."},{"key":"S1755020322000211_r19","first-page":"1","article-title":"La pr\u00e9vision: ses lois logiques, ses sources subjectives","volume":"7","author":"de Finetti","year":"1937","journal-title":"Annales de l\u2019Institut Henri Poincar\u00e9"},{"key":"S1755020322000211_r35","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"S1755020322000211_r4","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5229"},{"key":"S1755020322000211_r14","unstructured":"[14] Duarte, G. , Finkelstein, N. , Knox, D. , Mummolo, J. , & Shpitser, I. (2021). An automated approach to causal inference in discrete settings. Preprint, arXiv:2109.13471v1."},{"key":"S1755020322000211_r33","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/82.4.669"},{"key":"S1755020322000211_r6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.09.013"},{"key":"S1755020322000211_r16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00271-0"},{"key":"S1755020322000211_r24","unstructured":"[24] Ibeling, D. (2018). Causal modeling with probabilistic simulation models. In Bellodi E., and Shrijvers, T., editors. Proceedings of the 5 th International Workshop on Probabilistic Logic Programming (PLP). Ferrara: Italian Association for Artificial Intelligence, pp. 36\u201348."},{"key":"S1755020322000211_r5","first-page":"509","volume-title":"Probabilistic and Causal Inference: The Works of Judea Pearl","author":"Bareinboim","year":"2022"},{"key":"S1755020322000211_r12","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"S1755020322000211_r21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90039-1"},{"key":"S1755020322000211_r41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"S1755020322000211_r32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47012-2"},{"key":"S1755020322000211_r15","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1978.11994566"},{"key":"S1755020322000211_r25","doi-asserted-by":"crossref","unstructured":"[25] Ibeling, D. , & Icard, T. (2020). Probabilistic reasoning across the causal hierarchy. In Rossi, F., editor. Proceedings of the 34th AAAI Conference on Artificial Intelligence; revised as arXiv:2001.02889v5. Palo Alto, CA: Association for the Advancement of Artificial Intelligence.","DOI":"10.1609\/aaai.v34i06.6577"},{"key":"S1755020322000211_r3","unstructured":"[3] Abrahamsen, M. , Kleist, L. , & Miltzow, T. (2021). Training neural networks is \u2203\u211d-complete. In Ranzato, M., editor. Proceedings of the Thirty-Fifth Conference on Neural Information Processing Systems (NeurIPS). Vancouver: Curran Associates, Inc."},{"key":"S1755020322000211_r40","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71672-0"},{"key":"S1755020322000211_r13","unstructured":"[13] Darwiche, A. (2021). Causal inference using tractable circuits. In Ranzato, M., editor. Proceedings of the Thirty-Fifth Conference on Neural Information Processing Systems (NeurIPS). Vancouver: Curran Associates, Inc."},{"key":"S1755020322000211_r43","volume-title":"Causation, Prediction, and Search","author":"Spirtes","year":"2000"},{"key":"S1755020322000211_r10","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852053"},{"key":"S1755020322000211_r17","first-page":"1022","volume-title":"IEEE 61 st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Erickson","year":"2020"},{"key":"S1755020322000211_r28","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-2464(07)80018-8"},{"key":"S1755020322000211_r9","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"S1755020322000211_r22","doi-asserted-by":"publisher","DOI":"10.1613\/jair.648"},{"key":"S1755020322000211_r27","unstructured":"[27] Ibeling, D. , Icard, T. , Mierzewski, K. , & Moss\u00e9, M. (2022). Probing the quantitative\u2013qualitative divide in probabilistic reasoning. Unpublished manuscript."},{"key":"S1755020322000211_r11","doi-asserted-by":"crossref","unstructured":"[11] ten Cate, B. , Kolaitis, P. G. , & Othman, W. (2013). Data exchange with arithmetic operations. In Guerrini, G., editor. Proceedings of the 16 th International Conference on Extending Database Technology. New York: Association for Computing Machinery, pp. 537\u2013548.","DOI":"10.1145\/2452376.2452439"},{"key":"S1755020322000211_r45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01063886"},{"key":"S1755020322000211_r23","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0788"},{"key":"S1755020322000211_r18","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"S1755020322000211_r30","first-page":"441","volume-title":"Kreiseliana. About and Around Georg Kreisel","author":"Macintyre","year":"1995"},{"key":"S1755020322000211_r38","first-page":"334","volume-title":"International Symposium on Graph Drawing","author":"Schaefer","year":"2009"},{"key":"S1755020322000211_r2","doi-asserted-by":"crossref","unstructured":"[2] Abrahamsen, M. , Adamaszek, A. , & Miltzow, T. (2018). The art gallery problem is \u2203\u211d-complete. In Diakonikolas, I., and Kempe, D., editors. Proceedings of the 50 th Annual ACM SIGACT Symposium on Theory of Computing. New York: Association for Computing Machinery, pp. 65\u201373.","DOI":"10.1145\/3188745.3188868"},{"key":"S1755020322000211_r1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1049"},{"key":"S1755020322000211_r7","volume-title":"34 th Symposium on Theoretical Aspects of Computer Science (STACS 2017)","author":"Bil\u00f2","year":"2017"},{"key":"S1755020322000211_r42","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000189"},{"key":"S1755020322000211_r20","doi-asserted-by":"publisher","DOI":"10.1111\/j.2044-8317.2011.02037.x"},{"key":"S1755020322000211_r34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511803161"},{"key":"S1755020322000211_r8","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.10.006"},{"key":"S1755020322000211_r39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"S1755020322000211_r44","doi-asserted-by":"publisher","DOI":"10.1017\/S0266267100004132"},{"key":"S1755020322000211_r36","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2011.02.018"},{"key":"S1755020322000211_r37","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.4.589"},{"key":"S1755020322000211_r29","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698411"},{"key":"S1755020322000211_r31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00485695"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1755020322000211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T09:48:45Z","timestamp":1711446525000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1755020322000211\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,18]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S1755020322000211"],"URL":"https:\/\/doi.org\/10.1017\/s1755020322000211","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}