2026-07-25T13:18:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23521 2025-10-02T12:57:39Z ddc:004 open_access

Probabilistic and Causal Satisfiability: Constraining the Model Bläser, Markus Dörfler, Julian Liśkiewicz, Maciej van der Zander, Benito Existential theory of the real numbers Computational complexity Probabilistic logic Structural Causal Models 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Bläser and Julian Dörfler and Maciej Liśkiewicz and Benito van der Zander 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.144 urn:nbn:de:0030-drops-235214 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.144 eng https://creativecommons.org/licenses/by/4.0/legalcode