Search Results

Documents authored by van der Zander, Benito

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.144
Probabilistic and Causal Satisfiability: Constraining the Model

Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

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.
Cite as

Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander. Probabilistic and Causal Satisfiability: Constraining the Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 144:1-144:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.ICALP.2025.144,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Li\'{s}kiewicz, Maciej and van der Zander, Benito},
  title =	{{Probabilistic and Causal Satisfiability: Constraining the Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{144:1--144:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.144},
  URN =		{urn:nbn:de:0030-drops-235214},
  doi =		{10.4230/LIPIcs.ICALP.2025.144},
  annote =	{Keywords: Existential theory of the real numbers, Computational complexity, Probabilistic logic, Structural Causal Models}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.13
The Existential Theory of the Reals with Summation Operators

Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within Pearl’s Causal Hierarchy, van der Zander, Bläser, and Liśkiewicz [IJCAI 2023] introduce a new natural class, named succ-∃ℝ. This class can be viewed as a succinct variant of the well-studied class ∃ℝ based on the Existential Theory of the Reals (ETR). Analogously to ∃ℝ, succ-∃ℝ is an intermediate class between NEXP and EXPSPACE, the exponential versions of NP and PSPACE. The main contributions of this work are threefold. Firstly, we characterize the class succ-∃ℝ in terms of nondeterministic real Random-Access Machines (RAMs) and develop structural complexity theoretic results for real RAMs, including translation and hierarchy theorems. Notably, we demonstrate the separation of ∃ℝ and succ-∃ℝ. Secondly, we examine the complexity of model checking and satisfiability of fragments of existential second-order logic and probabilistic independence logic. We show succ-∃ℝ-completeness of several of these problems, for which the best-known complexity lower and upper bounds were previously NEXP-hardness and EXPSPACE, respectively. Thirdly, while succ-∃ℝ is characterized in terms of ordinary (non-succinct) ETR instances enriched by exponential sums and a mechanism to index exponentially many variables, in this paper, we prove that when only exponential sums are added, the corresponding class ∃ℝ^Σ is contained in PSPACE. We conjecture that this inclusion is strict, as this class is equivalent to adding a VNP-oracle to a polynomial time nondeterministic real RAM. Conversely, the addition of exponential products to ETR, yields PSPACE. Furthermore, we study the satisfiability problem for probabilistic reasoning, with the additional requirement of a small model, and prove that this problem is complete for ∃ℝ^Σ.
Cite as

Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander. The Existential Theory of the Reals with Summation Operators. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.ISAAC.2024.13,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Li\'{s}kiewicz, Maciej and van der Zander, Benito},
  title =	{{The Existential Theory of the Reals with Summation Operators}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.13},
  URN =		{urn:nbn:de:0030-drops-221407},
  doi =		{10.4230/LIPIcs.ISAAC.2024.13},
  annote =	{Keywords: Existential theory of the real numbers, Computational complexity, Probabilistic logic, Models of computation, Existential second order logic}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact