# Probabilistic and Causal Satisfiability: Constraining the Model

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 28 Apr 2025.

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

- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Partial Counterfactual Identification from Observational and Experimental Data](https://mlsanity.com/paper/2110.05690/) (2021)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models](https://mlsanity.com/paper/2303.18211/) (2023)
- [Probabilistic Reasoning across the Causal Hierarchy](https://mlsanity.com/paper/2001.02889/) (2020)
- [Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions](https://mlsanity.com/paper/2201.05666/) (2022)
- [Smoothing the gap between NP and ER](https://mlsanity.com/paper/1912.02278/) (2019)
- [Is Causal Reasoning Harder than Probabilistic Reasoning?](https://mlsanity.com/paper/2111.13936/) (2021)
- [The Hardness of Reasoning about Probabilities and Causality](https://mlsanity.com/paper/2305.09508/) (2023)
- [Probing the Quantitative-Qualitative Divide in Probabilistic Reasoning](https://mlsanity.com/paper/2307.05659/) (2023)
- [From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2405.07373/) (2024)
- [NEXP-completeness and Universal Hardness Results for Justification Logic](https://mlsanity.com/paper/1503.00362/) (2015)
- [On Probabilistic and Causal Reasoning with Summation Operators](https://mlsanity.com/paper/2405.03069/) (2024)
- [The Existential Theory of the Reals with Summation Operators](https://mlsanity.com/paper/2405.04697/) (2024)

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

- [Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2511.08091/) (2025)

## Abstract (arXiv)

We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables X1, X2,ldots over finite domains, the basic terms are probabilities of propositional formulas over atomic events Xi = xi, such as P(X1 = x1) or P(X1 = x1 vee X2 = x2). The basic terms can be combined using addition (yielding linear terms) or multiplication (polynomial terms). The probabilistic satisfiability problem asks whether a joint probability distribution satisfies a Boolean combination of (in)equalities over such terms. Fagin et al. (1990) showed that for basic and linear terms, this problem is NP-complete, making it no harder than Boolean satisfiability, while Moss'e et al. (2022) proved that for polynomial terms, it is complete for the existential theory of the reals. Pearl's Causal Hierarchy (PCH) extends the probabilistic setting with interventional and counterfactual reasoning, enriching the expressiveness of languages. However, Moss'e et al. (2022) found that satisfiability complexity remains unchanged. Van der Zander et al. (2023) showed that introducing a marginalization operator to languages induces a significant increase in complexity. We extend this line of work by adding two new dimensions to the problem by constraining the models. First, we fix the graph structure of the underlying structural causal model, motivated by settings like Pearl's do-calculus, and give a nearly complete landscape across different arithmetics and PCH levels. Second, we study small models. While earlier work showed that satisfiable instances admit polynomial-size models, this is no longer guaranteed with compact marginalization. We characterize the complexities of satisfiability under small-model constraints across different settings.