Gateways to Tractability for Satisfiability in Pearl’s Causal Hierarchy

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.

When we reason about cause and effect, we're often asking three types of questions: (1) 'What is likely to happen?', (2) 'What would happen if we intervened?', and (3) 'What would have happened if things had been different?'. Pearl's Causal Hierarchy is a well-known framework that organizes these three levels of causal thinking. However, the problem of figuring out whether a given set of causal statements is logically consistent is very hard. In most cases, no known algorithm can solve it efficiently, even when executed on powerful computers. This paper asks: are there special cases where the problem does become tractable? We answer this question in the positive, by showing that the problem admits efficient algorithms on instances of a certain structure. On the negative side, we demonstrate the limits of such a structure-based approach by identifying causal statements for which checking consistency remains hard nonetheless.