Probabilistic and Causal Satisfiability: Constraining the Model

Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander

Abstract: This paper investigates the computational complexity of Probabilistic and Causal Satisfiability under constraints such as fixed causal graph structures and limited model sizes. The authors identify significant complexity "jumps," demonstrating that adding causal constraints can elevate problems from NP-complete to classes like NEXP or the Existential Theory of the Reals.

What Problem Does This Paper Address?

In fields like AI, medicine, and economics, researchers often ask questions like: "Given the data we've seen, is it possible that drug X causes recovery Y?" This is a satisfiability problem: given a set of probabilistic or causal constraints (e.g., $P(Recovery | do(Drug)) > 0.7$), does there exist any mathematical model that satisfies them?

Example of hidden variables, observed distributions, and interventional probabilities in a causal model.

Previous research established the complexity for "unconstrained" models—where any probability distribution or causal mechanism is allowed. However, in the real world, we often have a causal graph (a Directed Acyclic Graph or DAG) that tells us which variables influence others. Alternatively, we might require small models that can be represented efficiently. The gap addressed here is how these two constraints—graph structure and model size—interact with different levels of Pearl’s Causal Hierarchy (PCH) and different types of arithmetic (linear vs. polynomial).

Methods

The paper is a theoretical tour de force in computational complexity. The authors use several key techniques:

  • Complexity Reductions: They prove hardness by reducing known difficult problems (like the Existential Theory of the Reals or Schönfinkel-Bernays sentences) to their specific satisfiability variants.
  • Logical Grammars: They define precise languages for three levels of reasoning: Probabilistic (Level 1), Interventional (Level 2), and Counterfactual (Level 3).
  • Compact Marginalization: A major focus is the $\Sigma$ (summation) operator, which allows for "compact" reasoning over many variables without exponentially expanding the formulas.
  • Algorithmic Bounds: They provide new algorithms, such as a PP (Probabilistic Polynomial time) algorithm for model checking and an NEXP algorithm for small-model satisfiability.

Key Insights and Ideas

  • The Graph Jump: One of the most striking findings is that fixing the graph structure makes the problem significantly harder. For interventional logic with linear arithmetic, the complexity jumps from PSPACE (in the unconstrained case) to NEXP (when the graph is fixed).
  • The Power of Counterfactuals: The authors show that Level 3 (counterfactual) languages are so expressive that they can actually "encode" the graph structure directly into the formula. This means that for counterfactuals, knowing the graph doesn't add extra complexity—it's already "baked in."
  • Small Models Aren't Always Simple: Usually, "small" means "easier." However, in the presence of compact marginalization, requiring a small model (one with only polynomially many non-zero entries) still results in high complexity (NEXP) for causal reasoning.
  • Arithmetic Matters: There is a fundamental divide between linear arithmetic (adding probabilities) and polynomial arithmetic (multiplying them). Polynomial arithmetic often pushes the problem into the realm of the Existential Theory of the Reals ($\exists\mathbb{R}$).

Key Results

The paper culminates in three definitive "Complexity Landscapes":

  1. Constrained Graphs: For the interventional layer, fixing the graph results in NEXP-completeness. For the probabilistic layer with polynomial arithmetic, it is succ-$\exists\mathbb{R}$-complete (a succinct version of the theory of the reals).
  2. Small Models: When models are forced to be small, the probabilistic layer sits in a new class called $\exists\mathbb{R}^\Sigma$, while the interventional and counterfactual layers remain NEXP-complete.
  3. Model Checking: The authors prove that checking if a specific Bayesian Network satisfies a polynomial formula is in $P^{PP}$, which is slightly harder than the counting class #P.

Limitations and Future Work

The authors acknowledge they haven't yet pinned down the exact complexity of the probabilistic layer with linear arithmetic and a fixed DAG ($Sat^{lin\langle\Sigma\rangle}_{DAG, L1}$), conjecturing it is $\exists\mathbb{R}^\Sigma$-complete. Furthermore, the study is limited to variables over discrete, finite domains; causal reasoning in continuous spaces likely involves different complexity bounds. Finally, while the paper establishes theoretical limits, translating these NEXP and $\exists\mathbb{R}$ results into efficient heuristics for AI researchers remains a major open challenge.

Summary updated

Abstract

We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables X₁, X₂,… over finite domains, the basic terms are probabilities of propositional formulas over atomic events X_i = x_i, such as ℙ(X₁ = x₁) or ℙ(X₁ = x₁ ∨ X₂ = x₂). 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. [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é et al. [Mossé 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 the languages. However, Mossé et al. [Mossé et al., 2022] found that the complexity of satisfiability remains unchanged. Van der Zander et al. [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.
BibTeX
@inproceedings{blaser2025probabilistic,
  author = {Markus Bläser and Julian Dörfler and Maciej Liskiewicz and Benito van der Zander},
  title = {{Probabilistic and Causal Satisfiability: Constraining the Model}},
  booktitle = {ICALP},
  year = {2025},
  url = {https://openreview.net/forum?id=7k5n2xPtag},
}
Figure