# Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 11 Nov 2025.

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

- [Partial Counterfactual Identification from Observational and Experimental Data](https://mlsanity.com/paper/2110.05690/) (2021)
- [Probabilistic Reasoning across the Causal Hierarchy](https://mlsanity.com/paper/2001.02889/) (2020)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [Is Causal Reasoning Harder than Probabilistic Reasoning?](https://mlsanity.com/paper/2111.13936/) (2021)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [The Complexity Landscape of Decompositional Parameters for ILP](https://mlsanity.com/paper/1809.00585/) (2018)
- [The Hardness of Reasoning about Probabilities and Causality](https://mlsanity.com/paper/2305.09508/) (2023)
- [The Existential Theory of the Reals as a Complexity Class: A Compendium](https://mlsanity.com/paper/2407.18006/) (2024)
- [Hedonic Games and Treewidth Revisited](https://mlsanity.com/paper/2202.06925/) (2022)
- [Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings](https://mlsanity.com/paper/2204.02902/) (2022)
- [From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy](https://mlsanity.com/paper/2405.07373/) (2024)
- [Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof](https://mlsanity.com/paper/2311.05913/) (2023)
- [Probabilistic and Causal Satisfiability: Constraining the Model](https://mlsanity.com/paper/2504.19944/) (2025)

## Abstract (arXiv)

Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.