Research map / Probabilistic and scientific modeling / Causal discovery
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper proves exact computational complexity of satisfiability for probabilistic, interventional, and counterfactual languages of Pearl's Causal Hierarchy when summation (marginalization) is allowed, showing strictly increasing complexity (NP^PP, PSPACE, NEXP) for basic/linear terms and succinct-reals completeness for polynomial terms.
Problem
Computational complexity of deciding satisfiability of formulas over probabilistic, interventional, and counterfactual terms in Pearl's Causal Hierarchy, especially when marginalization via summation is expressed compactly.
Approach
Introduces the unary summation operator into PCH languages and shows that it shifts satisfiability complexity from NP to NP^PP (probabilistic), PSPACE (interventional), and NEXP (counterfactual) for basic and linear terms, and resolves the counterfactual polynomial case as succR-complete.
Key results
- Satisfiability for basic and linear languages with summation is NP^PP-complete at the probabilistic layer, PSPACE-complete at the interventional layer, and NEXP-complete at the counterfactual layer.
- For polynomial languages with summation, counterfactual satisfiability is succR-complete, resolving an open problem.
- With full languages (addition, marginalization, multiplication), counterfactual satisfiability has the same complexity as probabilistic and causal levels.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add marginalization via Σ to basic or linear terms | Probabilistic satisfiability · Probabilistic PCH | complexity: NP-complete -> NP^ccPP-complete | Hurt |
| Add marginalization via Σ to basic or linear terms | Interventional satisfiability · Interventional PCH | complexity: NP-complete -> PSPACE-complete | Hurt |
| Add marginalization via Σ to basic or linear terms | Counterfactual satisfiability · Counterfactual PCH | complexity: NP-complete -> NEXP-complete | Hurt |
| Add marginalization via Σ to probabilistic polynomial terms | Polynomial satisfiability · Probabilistic PCH | complexity: succR-complete | No clear effect |
| Add marginalization via Σ to interventional polynomial terms | Polynomial satisfiability · Interventional PCH | complexity: succR-complete | No clear effect |
| Add marginalization via Σ to counterfactual polynomial terms | Polynomial satisfiability · Counterfactual PCH | complexity: ∃R-complete -> succR-complete | No clear effect |
| Remove negations from event primitives | Probabilistic basic/linear satisfiability with marginalization · Probabilistic PCH | complexity: NP^ccPP-complete -> NP-complete | Helped |
Surprising findings
- Full polynomial languages with summation have the same satisfiability complexity across all three PCH levels despite very different expressiveness.
- Removing negations from probabilistic formulas with summation drops the complexity from NP^PP to NP.
Limitations
- Results are worst-case complexity classifications and say nothing about practical algorithm performance.
- Relationship between NP^PP and existential reals classes is unknown; hardness results rely on widely believed separations of complexity classes.
Experimental setup
Baselines: Fagin-Halpern-Megiddo NP-completeness results Mossé et al. existential reals results Zander et al. succR results
Builds on: Fagin-Halpern-Megiddo logic of probability Pearl's Causal Hierarchy Mossé-Ibeling-Icard causal satisfiability Zander et al. succR results
Closest papers by meaning
- The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy (NeurIPS 2026 · similarity 0.87)
- Causal Abstractions, Categorically Unified (NeurIPS 2026 · similarity 0.86)
- COLD: Causal reasOning in cLosed Daily activities (NeurIPS 2024 · similarity 0.86)
- Does Reasoning Emerge? Examining the Probabilities of Causation in Large Language Models (NeurIPS 2024 · similarity 0.86)
- Exogenous Isomorphism for Counterfactual Identifiability (ICML 2025 · similarity 0.86)
- Unveiling Causal Reasoning in Large Language Models: Reality or Mirage? (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.