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?
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":
- 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).
- 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.
- 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