# The Hardness of Reasoning about Probabilities and Causality

arXiv: https://arxiv.org/abs/2305.09508 · HTML: https://mlsanity.com/paper/2305.09508/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 43 references that are in the map.
- First posted on arXiv 16 May 2023.

## Builds on (most cited first, 6 of 6)

- [Probabilistic Reasoning across the Causal Hierarchy](https://mlsanity.com/paper/2001.02889/) (2020)
- [The Computational Complexity of Structure-Based Causality](https://mlsanity.com/paper/1412.3076/) (2014)
- [Is Causal Reasoning Harder than Probabilistic Reasoning?](https://mlsanity.com/paper/2111.13936/) (2021)
- [Information and Computation](https://mlsanity.com/paper/1304.1428/) (2013)
- [On Classifying Continuous Constraint Satisfaction Problems](https://mlsanity.com/paper/2106.02397/) (2021)
- [NEXP-completeness and Universal Hardness Results for Justification Logic](https://mlsanity.com/paper/1503.00362/) (2015)

## Built on by (most cited first, 4 of 4)

- [On Probabilistic and Causal Reasoning with Summation Operators](https://mlsanity.com/paper/2405.03069/) (2024)
- [Modeling Discrimination with Causal Abstraction](https://mlsanity.com/paper/2501.08429/) (2025)
- [Probabilistic and Causal Satisfiability: Constraining the Model](https://mlsanity.com/paper/2504.19944/) (2025)
- [Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2511.08091/) (2025)

## Abstract (arXiv)

We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective. We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference. The main contribution of this work is establishing the exact computational complexity of these satisfiability problems. We introduce a new natural complexity class, named succexistsR, which can be viewed as a succinct variant of the well-studied class existsR, and show that the problems we consider are complete for succexistsR. Our results imply even stronger algorithmic limitations than were proven by Fagin, Halpern, and Megiddo (1990) and Moss'e, Ibeling, and Icard (2022) for some variants of the standard languages used commonly in probabilistic and causal inference.