From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
Authors: Julian Dörfler
Benito van der Zander
Markus Bläser
Maciej Liskiewicz
Venue: ICLR 2025 Poster (2025)
Keywords: complexity
causal reasoning
Pearl's Causal Hierarchy
Primary area: causal reasoning
TL;DR: What is the complexity of equation systems containing probabilistic and causal terms?

Abstract: The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given a system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas?  

Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NP^{PP}-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increasing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. On the other hand, in the case of full languages, i.e.~allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels, solving an open problem in the field.

Published as a conference paper at ICLR 2025
FROM PROBABILITY TO COUNTERFACTUALS: THE INCREASING COMPLEXITY OF SATISFIABILITY IN PEARL'S CAUSAL HIERARCHY
Julian Dörfier
Benito van der Zander"
Saarland University, Germany jdoerfler@cs, uni -saar maarllnnd land. de
University of Lübeek, Germany
b. vanderzanderruni www.euunnnnnneeeeeeeeeeeem luebeck..... de
Markus Bläser
Maciej Liskiewiez
Saarland University, Germany mb mblaeser&cs. .nniiii.iiiiii saarland. de
University of Lübeck, Germany
maciej.. naciej.liske
ABSTRACT
The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reason- ing: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas?
Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NPPP-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increas- ing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counter- factual level remains the same for the probabilistic and causal levels, solving an open problem in the field.
INTRODUCTION
The development of the modern causal theory in AI and empirical sciences has greatly benefited from an influential structured approach inference about causal phenomena, which based on a reasoning hierarchy named "Ladder of Causation". also often referred to as the "Pearl's Causal Hierarchy" (PCH) (Shpitteer & Pearl 2008 Pearl 2009 Bareinboim et al.) 2022), see also (Pearl & Mackenzie 2018) for gentle introduction to the topic). This three-level framework formalizes various types of reasoning that reflect the progressive sophistication of human thought regarding causation. arises from collection of causal mechanisms that model the "ground truth" of unobserved nature formalized within a Structural Causal Model (SCM). These mechanisms are then combined with three patterns of reasoning concerning observed phenomena expressed at the corresponding layers of the hierarchy, known as probabilistic (also called associational in the AI literature), interventional, and counterfactual (for formal definitions of these concepts, see Sec. 2
basic term at the probabilistic/asscciiioon layer is expressed as common probability, such a Fa g). This may represent queries like "How likely does patient have both diabetes (X x)
"Contribating equally first authors. i CContrbbuting equally last authors.
In our paper, we consider random variables over discrete, finite domains. By an event we mean proposi- tional formula over atomic events of the form X =r,, such as (X=r Y=y) or (X=r fy) Moreover, by P(Y=y, X=x), etc., mean, usually, P(X== ((X=AA==]) Finally by P(r,, y), abbreviate P(Y=y, X

---

Published as a conference paper at ICLR 2025
and high blood pressure (Y = From basic terms, we can build more complex terms by using additions (linear terms) or even arbitrary polynomials (polynomial terms). This can be combined with the use of unary summation operator, which allows to express marginalization in a compact way. Formulas at this layer consist of Boolean combinations of (in) (in)equalities of basic, linear, or, in the general case, polynomial terms. The interventional patterns extend the basic probability terms by allowing the use of Pearl's do-operator (Pearl, (009) which models an experiment like a Randomized Controlled Trial (Fisher, 1936). For instance, P( whict in general differs from P(yla), allows to ask hypothetical questions such as, e.g.. "How likely is it that patient's 's headache will be cured (Y y) if he or she takes aspirin (X = z)?". An example formula at this layer is P([r)y) = Σ> P(yla,,=) =)) which estimates the causal effect of the intervention do(X = x) (all patients take aspirin) on outcome variable Y = y (headache cure). It illustrates the use of the prominent back-door adjustment to eliminate the confounding effect of factor represented by the variable 2 (Pearl 2009). The basic terms at the highest level of the hierarchy enable us to formulate queries related counterfactual situations. For example, I[[X==]>> = Y Y=y')) expresses the probability that, for instance, a patient who did not receive a vaccine (X = x²) and died (Y = v') would have lived (Y y) if he she had been vaccinated (X 2²).
The computational complexity aspects of reasoning about uncertainty in this framework have been the subject of intensive studies in the past decades, especially in the case of probabilistic inference with the input probability distributions encoded by Bayesian networks (see, e.g., (Pearl) 1988; Cooper
1990; Dagum Luby 1993 Roth 1996 Park & Darwiche/ (004)). The main focus of our work is on the computational complexity of satisfiability problems and their validity counterparts which enable formulating precise assumptions on data and implications of causal explanations.
The problems take as input a Boolean combination of (in)equalities of terms at the PCH-layer of interest with the task to decide if there exists a satisfying SCM for the input formula or if the formula is valid for all SCMs, respectively. For example, for binary random variables X' and Y. the formula consisting of the single equality Σx E, P((X=x) A (X Y=y) A (X # V Y f)) = the language of the probabilistic laver is satisfied since there exists an SCM in which it is true (in fact, the formula holds in any SCM An SCM for inputs at this layer can be identified with the standard joint probability distribution, in our case, with P(X=x, Y=y), for x, y E (0.
The complexity of the studied satisfiability problems depends on the combination of two factors: (1) the PCH-layer to which the basic terms belong and (2) the operators which can be used to specify the (in)equalities of the input formula. The most basic operators are "4" "." (leading to linear, resp.. polynomial terms) and, mcaningful in causality, the unary summation operator used to express marginalization. Of interest is also conditioning, which will be discussed in our paper, as well. The main interest of our research is focused on the precise characterization of the computational complexity of satisfiability problems (and their validity counterparts) for languages of all PCH layers, combined with increasing the expressiveness of (in)equalities by enabling the use of more complex operators.
Related Work to our Study. In their seminal paper, Fagin, Halpem, and Megiddo (1990) explore the language of the lowest probabilistic layer of the PCH consisting of Boolean combinations of (in)equalities of basic and linear terms. Besides the complete axiomatization for the used logic, they show that the problem of deciding satisfiability is NP-complete indicating that the complexity is surprisingly worse than that of propositional logic. The authors subsequently extend the language to include (in)equalities of polynomial terms, aiming to facilitate reasoning about conditional probabilities. While they establish the existence of PSPACE algorithm for deciding whether such a formula is satisfiable, they leave the exact complexity open. Recently, Mossé, lbeling, and Icard (2022) resolved this issue by demonstrating that deciding satisfiability represents the well-studied class defined as the closure of the Existential Theory of the Reals (ETR) under polynomial-ting -oeeeii--mmeeeeeeeeeeeeeeeee many-one reductions. Furthermore, for the higher, more expressive PCH layers Mossé et al. prove that for (in)equalities of polynomial terms both at the interventional and the
compleete where EIR
A common and popular notation for the post-interventional probability is ([Y=yld[[X=s]) In this paper. however, the notation P([X=x)Y=V) since is more convenient for the analysis of counterfactuals. IIterestinngy, the instance can be seen as a result of reduction from the not-satisfiable Boolean formula (T b) (ā v b).
2

---

Published as a conference paper at ICLR 2025
counterfactual layer the decision problems still remain 3R-complete (we recall the definitions of the complexity classes in Sec. )
The languages used in these studies, and also in other works as, e.g., (Nilsson 1986 Georgakopoulos ct al. 1988 lbeling& & Icard 2020), are able to fully express probabilistic reasoning, resp.. inferring interventional and counterfactual predictions. In partieular, they allow one to express marginalization which is a common paradigm in this field. However, since the languages do not include the unary summation operator Σ, the abilities of expressing marginalization are relatively limited. Thus, for instance, to express the marginal distribution of a random variable Y over a subset of (binary) variables {Z,..... 3 S [X.....,.X) requires an expansion P(y. Z1=0,... 7...,,7--00 70= + ...... P(y, Zi Z1=1..... Zm=11 =1) of exponential size in m. Consequently, to analyze the complexity aspects of the problems under study, languages allowing the standard notation for encoding marginalization using the Σ operator are needed. In (van der Zander et al. 2023), the authors present first systematic study in this setting. They introduce a new natural complexity class, named succ-ER, which can be viewed as a succinct variant of ER, and show that the satisfiability for the (in) (in)equalities of polynomial terms, both at the probabilistic and interventional layer, are complete for succ-IR. They leave open the exact complexity for the counterfactual case. Moreover, the remaining variants (basic and linear terms) remain unexplored for all PCH layers.
as Ex.....m. Ply, 21...., 2m). ) an encoding without summation 8m
Our Contribution. The previous research establishes that, from computational perspective, many problems for interventional and counterfactual reasoning are not harder than for pure probabilistic reasoning. In our work, we show that the situation changes significantly if, to express marginalization, the common summation operator is used. Below we highlight our main contributions, partially summarized also in Table which involve complexity classes related to each other as follows m
ER
C
S
NP
PSPACE S NEXP S succ-3R C
EXPSPACE
(1)
NPPP
For combinations of (in)equalities of basic and linear terms, unlike pre- vious results, the compact summation for marginalization increases the com- plexity, depending on the level of the PCH: from NPPP-, through PSPACE-, to NEXP-completeness.
Terms
Li (prob.)
Ce (interv.)
La (count.)
basic
NP (a)
lin
poly
3R (b)
basic & marg. lin & marg.
The counterfactual satisfiability for (in)equalities of polynomial terms is succ-3R--complte, which solves the open problem in (van der Zander al.) 2023).
NPPP (1)
PSPACE (2)
NEXP (3)
poly & marg.
Succ-ER (c,
Table Completeness results for the satisfiability problems (a)
for C, (Fagin et al. 1990). for L2 and Ls (Mossé et al. [2022]
Accordingly, the validity problems for the languages above are complete for
(b) MMoséé et al. 2022). p, (c) for L1 and C2 [van der Zander et al.
2023). Our results (1)-(4): Theorem 4 8 9 resp. Theorem 10
the corresponding complement com- plexity classes. Interestingly, both satisfiability and validity for basic and linear languages with marginalization are PSPACE-complete at the interventional layer.
Our results demonstrate, for the first time, a strictly increasing complexity of reasoning across the PCH from probabilistic to causal to counterfactual reasoning- under the widely accepted assumption that the inclusions NPPP C PSPACE C NEXP in Eq. 1I above are proper. This relation, in the case of basic and linear languages with marginalization, aligns with the strength of their expressive power: From previous research, we know that the probabilistic languages are less expressive than the causal languages, and the causal languages, in turn, are less expressive than the corresponding counterfactual languages (for more discussion on this, see Sec.B).
In addition, the impact of establishing exact completeness results for probabilistic, causal, and counterfactual reasoning, as stated in our work, lies in their implications for algorithmic approaches
*The relationship between AR and NPPP unknown.
3

---

Published as a conference paper at ICLR 2025
to solve these problems. Under widely accepted complexity assumptions like, e.g., NP * PSPACE, the completeness of a problem highlights inherent limitations in applying algorithmic techniques, such dynamic programming, divide-and-conques SAT- or ILP-solvers, which are only effective for NP-complete problems. This, in turn, justifies the use of heuristics or algorithms of exponential worst-case complexity. Moreover, using the succ-FlR-ccompeeenne computational complexity of problems, we show that the complexity of counterfactual reasoning (for the most general queries) remains the same as for common probabilistic reasoning. This is quite surprising result, as the difference between the expressive power of both settings is huge.
as yardstick for measuring
Structure of the Paper. In Sec. we provide the main concepts of causation and define formally the problems considered in this work. We derive the complexity of satisfiability for basic and linear languages in Sec. Sec.B and for polynomial languages in Sec. Due space constraints, some proofs are omitted from the main text, and only proof outlines are provided. The complete proofs can be found in Sec. Ai in the appendix. Furthermore, Sec. B the appendix, provides an example illustrating the three types of reasoning in the framework of the PCH and in Sec. C we give formal definitions for the syntax and semantics of the languages of the hierarchy.
PRELIMINARIES
In this section, we give definitions of the main concepts of the theory of causation, including the Structural Causal Model (SCM), provide syntax and semantics for the languages of the PCH, and discuss the complexity classes used in the paper. To help understand the formal definitions, we encourage readers unfamiliar with the theory of causation to refer to S in the appendix, where we provide an example that, we hope, will make easier to understand the formal definitions and the intuitions behind them.
2.1 THE LANGUAGES OF CAUSAL HIERARCHY
We give here informal but reasonably precise description of the syntax and semantics of the languages studied in this paper. For formal definitions, see Section in the appendix.
We always consider discrete distributions and represent the values of the random variables as Val = {0, 1,..., C }}. We denote by X the set of variables used in a system and by capital letters denote the individual variables. We assume that Val is fixed and of cardinality at least two, and that all variables X, share the same domain Vol. A value of X, is often denoted by r; or a natural number. By an atomic event, we mean an event of the form X x. where X is a random variable and x is a value in the domain of X. The language Eppp of propositional formulas ó over atomic events is defined atomic intervention is either empty 1 or of the form X = x. An intervention formula is a conjunction of atomic interventions. The language of post-interventional events, denoted as Epost-inrs consists the formulas of the form [ax]ā where a is an intervention and 8 is in Epmp- The language of counterfactual events, Ecounterfuct- is the set Epost-int closed under A and -.
the closure of such events under the Boolean operators and -. The
The PCH consists of languages on three layers each of which is based on terms of the form P().). with = 1, 2.3. For the observational (associational) language (Layer 1), we have dj E Eprop- for the interventional language (Layer 2), we have &2 E Epeat-int and, for the counterfactual language (Layer 3), 6g E Ecommterfact- The expressive power and computational complexity properties of the languages depend largely on the operations that allowed to apply terms P(),). Allowing gradually more complex operators, we define the languages which are the subject of our studies. The terms for levels 1,2,3 are described as follows. The basic terms, denoted T.buse probabilities P(..) as, e.g., PP(X,=r) V X2=x2) in These or [(xx==1]X==0a) in T.hase From basic terms, we build more complex linear terms T.li by using additions and polynomial terms T. by using arbitrary polynomials. By T.t hase))) 7.(i((s) and 7.Pol(()) we denote the corresponding sets of terms when including a unary marginalization operator of the form Σ, t for a term t. In the summation, we have dummy variable which ranges over all values 0, ...
1. The summation Σn is a purely syntactical concept which represents the sum t|/ tP/=] +... t(c- - 1/z), where by t(y/s), we mean the expression in which all occurrences of x are replaced with
4

---

y. Published as a conference paper at ICLR 2025
value For example, for Val = {0, 1), the expression Σ, P(Y=1, semantically represents P(Y=1,X=0) + X-1=.
Now, let Lab {base, base(E)), lin, lin( poly())) denote the labels of all variants of lan- guages. Then for each * E Lab and = 1,2,3, we define the languages 2 of Boolean combinations of inequalities in standard way by the grammars: f :-= t I t' -f f f where t, t' are terms in T Although the languages and their operations can appear rather restricted, all the usual elements of probabilistic and causal formulas can be encoded in a natural way (see Section inntionniiin the appendix for more discussion).
To define the semanties, we use SCMs as in (Pearl 2009 Sec. 3.2). An SCM is tuple M (F.P, X. with exogenous variables U and endogenous variables X = {X1, .n F {Fi...., Fn) consists of functions such that F/ calculates the value of variable X, from the values (x, u) as F; (pa,, u,), w Pa; S X and U; S U. Pa; are all endogenous variables that directly influence X; and pa; are their value P specifies probability distribution of all exogenous variables U. Without loss of generality, we assume that the domains of exogenous variables are also discrete and finite. The functions F. are deterministic, i.e., the value every endogenous variable is uniquely determined given the values of the exogenous variables. Since the exogenous variables follow a probability distribution, this implies probability distribution over the endogenous variables.
For any basic intervention formula [X,=ı;] (which is our notation for Pearl's do-operator do(X,=x;)) we denote by Fx,=0, the functions obtained from F b replacing F; with the constant function (pa,; u,) == 24. We generalize this definition for any intervention a in natural way and denote as Fa the resulting functions. For any & E Epmp. we write F, u }= ip if y is satisfied for the values of X calculated from the values For any intervention a, we write F, u - [alp if F,,
u - if F, u 14 1b and (ii) F, F.uFo = A do And for all vi, 14,, 1/2 E Ecounterfacs we write (i) F,
if F.u u F 4/1 and F.u == th2. Finally, for & E Ecounterfaer. let Smn (16) {u F.uu } db be the set of values of U satisfying v.. For some expression e, we define the value [e] of the ex- pression given a model 27, recursively in a natural way, starting with basic terms as follows [P())] = (w) P(u) and, for d E Eprop [P(+10]]mn
[T(( A 6)] e0 (esxx/((())) [P)))] assum- ing that the expression is undefined if [F(6]] = We will sometimes write Por (b) instead of [ for short. For two expressions e and e2, we define 21 J= es S @2, iff, [ei] mn I [[ The semantics for negation and conjunction are defined in the usual way, giving the semantics for M1 += for any formula in Cz.
2.2 SATISFIABILITY FOR PCH LANGUAGES AND RELEVANT COMPLEXITY CLASSES
The (decision) satisfiability problems for languages of the PCH, denoted by SATS, with i = 1, 2, and * E Lab, take as input formula op in C and ask whether there cxists model 27 such that M | ş. Analogously, the validity problems for L; consist in deciding whether, for a given y. M = &p holds for all models 27. From the definitions, it is obvious that variants of the problems for the level i are at least as hard as their counterparts at a lower level.
We note, that the satisfiability problem (and its complement, the validity problem) does not assume anything about SCMs, including their structure. However, our languages allow queries of the form si > s. which enable to verify satisfiability, resp., the validity, for the formula yo in SCMs which satisfy properties expressed by the formula v5, whereby, e.g., v can encode a graph structure of the model. Thus, the formalism used in our work allows for the formulation of wide range of queries.
To measure the computational complexity of SAT2, a central role play the following, well-known Boolean complexity classes NP, PSPACE, NEXP, and EXPSPACE (for formal definitions see, e.g., Arora & Barak (2009)) Recent research has shown that the precise complexity of several natural satisfability problems can be expressed in terms of the classes over the real numbers 3R and SI. For a comprehensive compendium on FIR, see (Schaefer et al. (2024). Recall, that the existential theory of the reals (ETR) the set of true sentences of the form
3x ... 3xn ( .1....,................. Zn),
'ee consider recursive models, that is, we assume the endogenous variables are ordered such that variable X, (i.c. function F.) is not affected by any X, with j > i. SSCMs are often represented graphs, in which case the variables Pa, can be represented as the parents of variable X, However, the definition using functions does not refer any graphs.
5

---

Published as a conference paper at ICLR 2025
where t is quantifier-fre free Boolean formula over the basis {V, A, }} and signature consisting of the constants and 1, the functional symbols + and and the relational symbols <, S. and =. The sentence is interpreted over the real numbers in the standard way. The theory forms its own complexity class FIR which is defined as the closure of ETR under polynomial time many-one reductions (Grigoriev & Vorobjov] 1988 Canny 1988 [Schaefer] 2009; Schaefer et al.) 2024 The significance of this class lies in the exceptional expressiveness of the ETR, enabling the representation of numerous natural problems across computational geometry (Abrahamsen et al. [2018] McDiarmid & Müller 2013 Cardinal 2015). Machine Learning and Artificial Intelligence (Abrahamsen et al. 2021; et al., 2022 van der Zander et al. 2023 Dörfler et al., 2024). game theory (Bilò &
Mavronicolas 2017
2017 Garg et al. 2018), and various other domains.
succinct variant of ETR, denoted as succ-ETR,, and the corresponding class succ- have been introduced by van der Zander et al. (2023). Bucc-ETR&& is the set of all Boolean circuits C' that encode a true sentence as in (2) as follows. Assume that C' computes a function (0. 1) - {0. 1.MM..M..... {0, 1 represents the node set of the tree underlying yp and C(i) is encoding of the description of node i, consisting of the label if its parent, and its two children. The variables in yp are T1, Z2N. As in the case of FR, to succ-EIR belong all languages which are polynomial time many-one reducible to succ-ETR, ETR.
M Then
For two computational problems A, B, we will write A Sp B if A can be reduced to B in polynomial time, which means A is not harder to solve than B. A problem A is complete for complexity class C, if A E C and, for every other problem B C, it holds B Sp A. By co-C, we denote the class of all problems A such that their complements A belong to C.
3. THE INCREASING COMPLEXITY OF SATISFIABILITY IN THE PCH FOR LINEAR LANGUAGES WITH MARGINALIZATION
The expressive power of the languages LT with * E (base, lin, poly) and the layers 1,2.3 has been the subject of intensive research. is well known, see e.g. (Pearl, 22099] Bareinboim et al. 2022] Mossé et al. 2022; Suppes & Zanotti 198T). that they form strict hicrarchies along two dimensions: First, on each layer i, the languages Dimee Ll and Coady have increasing expressiveness; Second, for every * E (base, lin, poly)
5 C S 23
(3)
where the proper inclusion means that the language 4 is less expressive than Li+1- Note that since adding marginalization does not change the expressiveness of the language Ct, the strict inclusions in (3) hold also for * E {base(>)), lin (ol)))))
To prove such a proper inclusion, it suffices to show two SCMs that are indistinguishable in the less expressive language, but that can be distinguished by some formula in the more expressive language. E.g.. the SCMs: 2N- (F. U. and DY' (F', P, U, U) with binary variables
U (U, U2)
[X,, x2). probabilities P(U, 0) = 1/2, and mechanism F: X; == U.
resp. Fi: X1 = U2U2 + (1 (1) U2), X₂ : + (5(1-1)) U2) have the same distributions Par (X1, (X1,X2). Thus, M and NN are indistinguishable in any language of the probabilistic layer. On the other hand, after the intervention X, = 1, we get Pox [o,((X[=|]xx=1)
Pon (X,, X2)
1/2 and Pay ([X, ([x==]Xx==1)
3/4. Then, e.g., for the Ch formula & P[[XI=1|X,-1] -(x=,,]{x==0,, we have 2N F s. but DD # O which means that & distinguishes MN from MY'
This section focuses the basic and linear languages across the PCH (the case of polynomial languages will be discussed in Sec. seeparatlly. As mentioned in the introduction. a comparison of these languages from the perspective of computational complexity reveals surprisingly different properties than the ones described above. For basic and linear languages disallowing marginalization, the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels: problems SAT and SAT for all i = 1, 2, 3 are NP-complete, i.e., as hard reasoning about propositional logic formulas ((Fagin et al. 1990; Mossé et al. 2022). ef. also I.. In this section, we show that the situation changes drastically when marginalization is allowed: satisfiability buse and SAT E, become NPPP., PSPACE-, resp. NEXP MEXP-complete depending on the level i. This demonstrates the first strictly increasing complexity of reasoning across the PCH, assuming the widely accepted assumption that the inclusions NPPP C PSPACE C NEXP are proper.
problems S SAT C.

---

Published as a conference paper at ICLR 2025
3.1 THE PROBABILISTIC (OBSERVATIONAL) LEVEL
Marginalization via the summation operator, combined with the language expressing events ó on a specific level of the PCH, increases the complexity of reasoning to varying degrees, depending on the level. the probabilistic case, it jumps from NP- HIPP--comlettnnee since the atomic terms P()) can contain Boolean formulas 8, which, combined with the summation operator, allows to count the number of all satisfying assignments of a Boolean formula by summing over all possible values for the random variables in the formula. Determining this count is the canonical PP- PP-complete problem, so evaluating the equations given a model is PP-hard. From this, together with the need of finding a lin(s)) L1 are NPPP ucpP-cceeeet..
model, we will conclude in this section that SAT C1
base(s) and SAT21
We start with a technical but useful fact that a sum in the probabilistic language can be partitioned into a sum over probabilities and a sum over purely logical terms. This generalizes the property shown by Fagin et al. (1990) Lemma 2.3 for languages without the summation operator.
Fact Let 8 Eprop be a propositional formula over variables Xiy....,X, Ex.," ...E. ...,,, P(O) is equal to E..... Ls, Pa....k. Lx., E..,... Ez,, S2...2, 2. (Tin....,, ;4 where the range of the sums the entire domain, Pa.... is the probability of i A.... A &t) and 02, (Niyy.... ... Iix, a function that returns 1 if the implication (X1=i) -1 1 A... A X, xn 8(I.))...,,3 [..) ) a tautology and O otherwise.
A sum
The canonical satisfiability problem SAT, where instances consist of Boolean formulas in propositional logic, plays key role in broad range of research fields, since all problems in NP, including many real-world tasks can be naturally reduced to it. As discussed earlier, SAT and SAT do not provide greater modeling power than SAT. Enabling the use of summation significantly changes this situation: below we demonstrate the expressiveness bas(())( ssowing that any problem in NPPP can be reduced to it in polynomial time.
Lemma 3. SAT base(z)
is NpPP-hard. -hard.
Proof. The canonical NPPP -complete problem E-MajSat is deciding the satisfiability of formula db B21 ... In #y1 o 2 2n-12 ie. deciding whether the Boolcan formula e has a majority of satisfying assignments to Boolean variables Yi after choosing Boolean variables z; existen- tially (Littman et al. 1998). We will reduce this to SaThae(()) Let there be 2n random variables X1,..., X,, Vi...., Yn associated with the Boolean variables. Assume w.l.o.g. that these random variables have domain {0. Let ø' be the formula & after replacing Boolcan variable ø, with X, = 0 and y, with Y, =yy-
Consider the probabilistic inequality sp En, ... Ey. P((d) 2 2n-1 whereby 2n is encoded as En -...,, PT(T). The left hand side equals
Er. Ez, Eg, LE.. Phi tn. In E E 82 S Sr. Sn (31 ........ Un)
according to Fact 2 Since the last sum ranges over all values of yıs it counts the number of satisfying assignments to given d.. Writing this count as #y fn)), the expression becomes: En. -E., Eg -Eg, Pi.......h Hy ..I.)..
Since #y .)..,)) does not depend on J. we can write the expression as Ee, ... Ex, Pa..... (0(0 ..)) whereby Ps.
= =E,, Eg, Ps......01....
If lb is satisfiable, there is an assignment æ1. 2n with #y(Ø(0 ... .n)) 2 2n-1 If we set Pa..... and every other probability Paç...;; 0, to is satisfied.
4 is satisfiable, let # Hyl0(xpan .....azz)
I ImeR
mmaz
assignment that maximizes Σn Ex, Pāi...., # (0(( ...)) S
the
Then 2 <
Ee, ... Ee, Pai..., a. #y (0(ffau .....aar) = (Ee, Ee, pa.....)) #u(o(o x.aa))) # #y(o ....x"aa, x)aa))) Hence v satisfied for ximan
x. man
Theorem 4. For probabilistic reasoning, the satisfiability problems SAT and SAT for the basic and linear languages respectively, are -compleee
base(s)
lin(s)
7

---

Proof idea: Having Lemma B it remains to prove that the problem is in NPPP. To this aim, we show that any satisfiable instance has a solution of polynomial size: we rewrite the sums Ez,, ... Ex., P(ò) in the expressions according Fact which allows to encode the instance system of m linear equations with unknown coefficients ? where m is bounded by the instance size. Such system has non-negative solution with at most entries positive of polynomial size. Then, we guess non -onddtttrmiiistcaally such solutions and verify its correctness estimating the values Published as a conference paper at ICLR 2025
Ex., ... ..,,,, ōg,dn &n (Zi,, ... Dtj) using the PP oracle. A full proof, as for all further proof ideas, can be found in the appendix.
Remark 5. NP?P is the class describing the complexity of another, relevant primitive of the proba- bilistic reasoning which consists finding the Maximun a Posteriori Hypothesis (MAP). To study its computational complexity, the corresponding decision problem defined which asks for a given Bayesian network B (9, PB), where probability P8. factorizes according the structure of network 9, a rational number т, evidence e, and some subset of variables Q2 there is an instantiation q to Q such that Pg(q. e) = EE (.yy..yee T. It is well known that the problem is NPPP-complete Roth 1996 Park & Darwiche 2004).
Finally, we draw our attention to the impact of negation on the complexity of reasoning for such languages of the probabilistic layer. The hardness of SAT li((s)) depends on negations in the Boolean formulas 5 of basic terms P(5), which make it difficult to count all satisfying assignments. Without negations, marginalization just removes variables, e.g. P(X=xAX YY= becomes P(Y=y). This observation leads to the following:
C. Proposition 6. EAT hase))))))) and (ir are NP-complete if the primitives in Epost-int are restricted to not contain negations.
3.2 THE INTERVENTIONAL (CAUSAL) LEVEL
In causal formulas, one can perform interventions to set the value of a variable, which can recursively affect the value of all endogenous variables that depend on the intervened variable. This naturally corresponds to the choice of a variable value by an existential or universal quantifier in a Boolean formula, since in a Boolean formula with multiple quantifiers, the value chosen by each quantifier can depend on the values chosen by earlier quantifiers. Thus, an interventional equation can encode quantified Boolean formula. This makes SAT(((()) PSPACE-complete.
(in(=) PSPACE-hard. As we will show below, it even C2
Lemma 7. SArhaa hase(s) (s) is PSPACE hard.
Proof. We reduce from the canonical PSPACE-complets problem QBF Let Q Q2 ... Qu
be quantified Boolean formula with arbitrary quantifiers Q1. ......... On E (3,7). We introduce Boolean random variables X {X1...., to represent the values of the variables and denote by Y (Y,, ..) S X the universally quantified variables. In Lg one can enforce an ordering X1 < X2 < ... X, of variables, i.e. variable X; can only depend on variables X, with < i. The proof of this property, formulated in Lemma 13 can be found in the appendix. Our only further constraint is
Σy p(())))) = 2*
where ei is obtained from by replacing positive literals F, by X; 1 and negative literals I7 by X; 0.
Suppose the constructed SAT (u())) formula is satisfied by model Mt. We show that Q Q222 ... Qn / satisfibll.. Each probability implicitly sums over all possible values u of the exogenous variables. Fix one such with positive probability. Combined with X1 .... X,, this implies all random variables now deterministically depend only on any of the previous variables. Equation (4) enforces P((y)=))= 1 for every choice of y and thus simulates the Y being universally quantified. As the existential variables F,, we then choose the value I; of X, which can only depend on X, with i. The formula v/ and thus ib is then satisfied due to P ((y)))) = 1.
On the other hand, suppose Q1 Q22² ... Qn 2b is satisfiable, We create a deterministic model Mt as follows: The value of existentially quantified variables X; is then computed by the function
8

---

Published as a conference paper at ICLR 2025
Fi 1111) defined as the existentially chosen value when the previous variables set to Di...., 2i-1- The values of the universally quantified variables do not matter since we intervene on them before every occurrence. This satisfies the required order of variables and, since is satisfied, we have P( (()))/) = 1, for every choice of the universally quantified variables y, thus satisfying equation
lit Theorem 8. For causal reasoning, the satisfiaillity problems SAThuse()) and SAT .for the basic and linear languages respectively, are PSPACE-complete.
(in(s) Proof idea: After Lemma 7 we only have to show that SAT is in PSPACE. For the proof details, see the appendix. The basiC idea is to evaluate interventions one at time without storing the entire model because each primitive can only contain one intervention. For each sum, we only need store
the total probability of all its primitives, and increment this probability, if a new intervention satisfies some the primitives.
As with Si there can only be polynomially many exogenous variable assignments u with non- zero probability Pu, which are independent of each other and can be guessed aonddtermiinistiallly... We can also guess a causal order of the endogenous variables, such that variables can only depend on the variables preceding them the causal order. This causal order allows one to guess the variables affected by any intervention in sound way.
We enumerate exogenous variable assignments u, each having probability Pu. Recursively, we can enumerate all possible interventions a, which yield the values of the endogenous variables, which- the exogenous variables-ale also have probability Pu. Then we count for each sum how many of its primitives are satisfied by a and x, and increment the accumulated value of the sum by Pu for each.
After this enumeration, we know the numeric value of every sum, and can verify the resulting equation system.
3.3 THE COUNTERFACTUAL LEVEL
On the counterfactual level, one perform multiple interventions, and thus compare different functions of the model to each other. Hence, the formulas can only be evaluated if the entire, exponential-sized model is known. Thus deciding the satisfiability requires exponential time and non-determinism find the model, making SAT(i(())
(i(()) NEXP-complete.
Theorem 9. For counterfactual reasoning, the satisfiability problems the basic and linear languages respectively, are NEXP-complete.
SAT base(() and SAT lints) for
Proof idea: This NEXP- -hardness follows from reduction from the NEXP- problem of checking satisfiability of a Schönfinkel -enonninnll-BBeayys sentence to the satisfiability of SAThue((s) These are first-order logic formulas of the form 3 where v cannot contain any quantifiers or functions. The and y are encoded as Boolean random variables, where the existentially quantified x are encoded into the existence of satisfying SCM, while the universally quantified y are encoded by marginalization, i.c. a condition Σy Pyy]'') = 2n for some formula v derived from & and where n denotes the number of variables y. The counterfactuals now allow us to ensure that the random variables Rt representing the relations within v deterministically depend inputs by comparing whether R2 changes between an intervention on all variables (except R2) versus an intervention only its dependencies. Marginalization finally allows to combine these exponentially many checks for all possible values all variables into single equation.
their respective
The containment in NEXP follows from expanding the formulas with sums exponentially larger formulas without sums.
THE COMPLEXITY OF SATISFIABILITY FOR POLYNOMIAL LANGUAGES WITH MARGINALIZATION
Van der Zander et al. 2023) prove that SAT noly and Sof are complete for succ-3R whenever E,
the basic terms allowed also contain conditional probabilities. They, however, leave open the

---

Published as a conference paper at ICLR 2025
exact complexity status of SAT (ob(())) conditional probabilities, which proves its succ-Jlk- coopllt--ommletennss.
La Here show that the problem is in succ-3R, with and without
Theorem 10. SaT E succ-ER, This also holds true if we allow the basic terms to contain
conditional probabilities.
Proof idea: Bläser et al. 2024) introduced the NEXP machine model, where succ-]R is precisely the set of all languages decidable by exponential-iig non-deterministic real RAMs. Combined with the algorithm proving Sar22 E MR (however without subtractions or conditional probabilities) from Mossé et al. (022) and the classification 3R NPreal from Frickson et al. (2022), i.e. AR being the set of all languages decidable by polynomial-time the unary sums explicitly and then run the non-deterministic real RAM algorithm for the resulting SA instance. Special care has to be taken in dealing with subtractions conditional probabilities, here we use a trick by T'siitn, the details of which can be found in Lemma 15 in the appendix. n
non-deterministic real RAMs, we can expand
We note that lieling et al. (2024 Theorem 3) independently obtained variant of the above result, also using the machine characterization of succ-3R given by Bläser et al. (004)).
Remark 11. It can be shown that the hardness proofs for SAT not need conditional probabilities in the basic terms.
SAT
and SAT do SA
poly(=) L2
5 DISCUSSION
This work studies the computational complexities of satisfiability problems for languages at all levels of the PCH. Our new completeness results nicely extend and complement the previous achievements by Fagin et al. (1990), Mossé et al.] (2022), van der Zander et al. (2023), and Blaäsr et al. (2024). The main focus of our research was on languages allowing the use marginalization which is expressed in the languages by summation operator Σ over the domain of the random variables. This captures the standard notation commonly used in probabilistic and causal inference.
A very interesting feature of the satisfiability problems for the full, polynomial languages is the following property. For both variants, with and without summation operators, while the expressive powers of the corresponding languages differ, the complexities of the corresponding satisfiability problems at all three levels of the PCH are the same. Interestingly. the same holds for linear languages without marginalization, too (ef. Table [T). We find that the situation changes drastically in the case of linear languages allowing the summation operator >. One of our main results characterizes the complexities of SAT [n(ss) SAT [x)) and S
lin(s)) problems NPPP, PSPACE, and NEXP-complete
respectively. The analogous completeness results hold for SAT buse(z)
Another interesting feature is that the completeness results for linear languages are expressed in terms of standard Boolean classes while the completeness of satisfiability for languages involving polynomials over the probabilities requires classes over the reals.
As mentioned in Section 2.2 the formulas can also encode graph structures. One might ask whether the computational complexity changes if the graph is not encoded in the formulas but is given directly graph in the input, which is common setting in causal reasoning. Also to show the complexity upper-bound on the probabilistic and interventional linear languages, we used a fact that it is sufficient only consider models of polynomial size for these languages (cf. Footnote 8 in the appendix). Here one might wonder what is the complexity of restricting oneself to polynomially-size models for the other languages? We answer both questions in follow-up paper (Bläser et al. 2025
ACKNOWLEDGMENTS
This work was supported by the Deutsche Forschungsgemeinschaftt (DFG) grant 471183316 (ZA 1244/1-1). We thank Till Tantau for the key idea that made the proof of the NPPP- -hardness of SAt possible.
(inss)
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem FR- complete. In Proc. 50th ACM SIGACT Symposium on Theory of Computing (STOC), pp. 65-73, 2018.
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is Romclleete.. In Proc. 35th International Conference on Neural Information Processing Systems (NeurIPS), pp. 18293-18306, 2021.
Antonis Achilleos. NEXP-co cexp-completeness and universal hardness results for justification logic. In Proc. International Computer Science Symposium Russia, pp. 27-52. Springer, 2015.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009,
Elias Bareinboim, Juan D. Correa, Duligur lbeling, and Thomas Icard. On Pearl's 's Hierarchy and the Foundations of Causal Inference, pp. 507-556. Association for Computing Machinery, New York, NY, USA, 2022.
Vittorio Bilô and Marios Mavronicolas. -IR-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In Proc. 34th Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl-LeibbizzZeentne
fuer Informatik, 2017.
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, and Benito van der Zander. The existential theory of the reals with summation operators. In Proc. 35th International Symposium on Algorithmss and Computation (ISAAC). 2024.
Markus Bläser, Julian Dörfler, Maciej Liskiewicz, and Benito van der Zander. Probabilistic and causal satisfiability: Constraining the model. In 52st International Colloquium on Automala, Languages, and Programming (ICALP 2025), L.IPlss. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2025. Available as ArXiv TR 2905.19944.
John Canny. Some algebraic and geometric computations in PSPACE. In Proc. 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 460-467. ACM, 1988.
Jean Cardinal. Computational geometry column 62. ACM SIGACT News, 46(():699-7, 2015.
Gregory F Cooper. The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42(2-3):393-405, 1990.
Paul Dagum and Michael Luby. Approximating probabilistii inference in Bayesian belief networks is NP-hard. Artificial Intelligence, 60(1):141-153, 1993.
Julian Dörfler, Benito van der Zander, Markus Bläser, and Maciej LiSkiewicz. On the complexity of identification in linear structural causal models. In Proc. 38th Annual Conference on Neural Information Processing Systems (NeurIPS). 2024.
Jeff Erickson, Ivor Van Der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ER.
SIAM Journal on Computing, pp. FOCS20-102, 2022.
Ronald Fagin, Joseph Halpern, and Nimrod Megiddo. A logie for reasoning about probabilities. Information and Computation, (((1-2):8--128. 1990.
Ronald Aylmer Fisher. Design of experiments. British Medical Journal, 1(3923):554, 1936.
Jugal Garg, Ruta Mehta, Vijay V Vazirani, and Sadra Yazdanbod. 3R-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Transactions on Economics and Computation (TEAC), 601):1-23, 2018.
George Georgakopoulos, Dimitris Kavvadias, and Christos H Papadimitriou. Probabilistic satisfiabil- ity. Journal of Complexity, 4(1):1-11, 1988.
Dima Grigoriev and Nicolai Vorobjov. Solving systems of polynomial inequalities in subexponential time. Journal of Symbolic Computation, 5(1/2):37-64 1988.
11

---

Published as a conference paper at ICLR 2025
Duligur lbeling and Thomas Icard. Probabilistic reasoning across the causal hierarchy. In Proc 34th AAAI Conference on Artificial Intelligence, AAAI, pp. 10170-10177. AAAI Press, 2020.
Duligur Ibeling, Thomas Icard, and Milan Mossé. On probabilistic and causal reasoning with summation operators. Journal of Logic and Computation, pp. exae068, 2024.
Harry Lewis. Complexity results for classes of quantificational formulas. Journal of Computer and System Sciences, 21(3):317- -533, 1980.
Michael L Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilistic planning. Journal of Artificial Intelligence Research, 9:1-36, 1998.
Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, (03(1):114-144)) 2013.
Milan Mossé, Duligur lbeling, and Thomas Icard. causal reasoning harder than probabilistic reasoning? The Review of Symbolic Logic, pp. 1 1-26, 2022.
Nils J Nilsson. Probabilisticc logic. Artificial Intelligence, 28(1):71-87, 1986.
James D Park and Adnan Darwiche. Complexity results and approximation strategies for MAP explanations. Journal of Artificial Intelligence Research, 21:101-133, 2004.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.
Judea Pearl. Causality. Cambridge University Press, 2009.
Judea Pearl and Dana Mackenzie. The book of why: the new science of cause and effect. Basic books, 2018.
Dan Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1-2):273-301 1996.
Mareus Schaefer. Complexity some geometric and topological problems. In Proc. International Symposium on Graph Drawing, pp. 934-344. Springer, 2009.
Marcus Schaefer, Jean Cardinal, and Tillmann Miltzow. The existential theory of the reals complexity class: A compendium. arXiv preprint arXiv:2407. 18006, 2024.
Ilya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. Journal of Machine Learning Research, 19Sep):194111999 2008
Patrick Suppes and Mario Zanotti. When are probabilistic explanations possible? Synthese, 48: 191-199, 1981.
Benito van der Zander, Markus Bläser, and Maciej Liškiewicz. The hardness of reasoning about probabilities and causality. Proc. Joint Conference on Artificial Intelligence (IJCAI), 2023.
Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In Proc. International Conference Machine Learning (ICLM), pp. 26548 26558. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2025
A TECHNICAL DETAILS AND PROOFS
In this section we complete proofs of our main results (announced in Table in the Introduction): Theorem 8 g and Theorem [0. which were partially presented outlined the main part of the
paper. More precisely, Theorem will follow from Lemma 3 and 12 Theorem 8 from Lemmal 7 and
14. Theorem will be proved in Sec. A.3 and the proof of Theorem will be presented in Sec. A.4
We also show the proof of Fact 2 and of Proposition
A.1
PROOFS OF SECTION 3.1
We first prove Fact
Theorem
will follow from Lemma and Lemma
presented below.
Proof of Fact 2
Σ mi
Σ Zit
P(ő) is equivalent to
P((XI=á A... A -x= ^ ^
may
$1
2n
P((X1=$1 A... ......... =& ^
31
Zit
Σ
Σ
Pā.... dāg Ss Bn (Dig ... Fzt)
Ziz
Pai...
Σ
Σ
(5)
&1
2n
Rij
which completes the proof.
Since the second sums in (5) only depend on ê fn and not P they can be calculated without knowing the probability distribution. Due to the dependency on σ ... &n the expression cannot be simplified further in general. However, if event d in P(5) contains constant events like X;, = O but only events X,, = Fi depending on the summation variables Zi,, the sum always includes one iteration where the event occurs and sum En,, ... Ex;; Ōz (.ii)...,, Ti,, is constant and effectively counts the number of satisfying assignments to the formula Since the sum Σg, ... Ee. Ps...... &n. is always the original sum Ex, ... Σn,, ... P()) also counts the number of satisfying assignments.
iterations where does not. Thus the
Bu(s)) Lemma 12. SAT is in NPPP.
Proof. First we need to show that satisfiable instances have solutions of polynomial size. We write each (sum of a) primitive in the arithmetic expressions as
E...EPat....a
_...
Σ.. > Sa
81
Fij
according to Fact
The value of all P. can be encoded as vector 17 E Re. For each .i,..., &n. the sum Ex,, ... E.,, 82, (Zij is a constant integer & d. Suppose there are m such sums or primitives in the instance, whose values can be encoded as a matrix A E maxe".
Then the value of every sum in the instance is given by the vector Ap E g
There exists a non-negative vector q E Q containing at most m non-zero entries with Ag = Ap (Lemma 2.5 in Fagin et al. (1990h). By including constraint Σx, ...E,. Paj..... = 1 when constructing the matrix A, we can ensure that all values in q are valid probabilities. is polynomial sized solution and can be guessed non-deterministically.
For this solution, the sum Ex, Σ Pa. can then be evaluated (over all non-zero entries P in polynomial time. Each sum Ex,, Ex,, d da (Kig ( .i,) can be evaluated using
13

---

Published as a conference paper at ICLR 2025
the PP oracle because PP oracle is equivalent #P oracle which count the number of satisfying assignments of 6.
Finally, we give the proof of Proposition 6
Proof of Proposition 6 In the proof of Lemma 12 we require a PP-oracle to evaluate the sum Ees, ... Ex, 02.... F which counts the number of assignments Tap that make 1X1=11A A ;n) - 8(zi,...., Fi,) tautology for given .;.
Without negations, there are also no disjunctions, some variable to some constant, X; = j. or to some variable X; 2i, used in the summation, For any constant X; = j. we check whether a; = j. that is false, the number of satisfying assignments to 8 is zero. From any condition X; = Fiy. we learn that zi; has to be equal to d;,. If there is any contradiction, ic.. X, = Ií, X₂ = 2;, and 2; o .k. the number of assignments also zero. This determines the value of each ri, occurring in 6 and makes 5 tautology.
consists of a conjunction of terms that compare
leaves the value of Fi, not occurring undefined, but those do not affect and can be chosen arbitrarily, the number of assignments is just multiplied by the size of the domain for each not-occurring variable.
This can be evaluated in polynomial time, so the complexity is reduced to NP = NP.
The problems remain NP-hard since Boolean formula can be encoded in the language Lhase of combinations Boolean inequalities. Each Boolean variable x is replaced by P(X) > for corresponding random variable X. For example, 3-SAT instance like (Iay, - V T A (I42, V - V -i22g)) A... can be encoded as (P(X,,.) > 0V -P(X,, > 0 P(X,,) 0) (P(Xig)) 0 -P((iza) OV -P(X,2a) 0) A ... which clearly has the same
satisfiability.
A.2 PROOFS OF SECTION 3.2
We first prove the property stated in lemma below. Lemma 13. In L2 one can encode a causal ordering.
Proof. Given (in- )equalitess in L2, we add a new variable and add to each primitive the intervention [C = 0j. This does not change the satisfiability of (in- (in-)equalities.
Given a causal order V,, < V2, < we add c equations for each variable Vi, >
for k l...,, V..,- =kk
The equations ensure, that one variable changed, and C is set, the next variable in the causal ordering has the same value, thus fixing an order from the first to the last variable.
Theorem & follows from Lemda from:
Lemma 14. SAT (i(()) is in PSPACE.
Proof. We need to show that Algorithm correct and in PSPACE. The basic idea of the algorithm that rather than guessing a model and evaluating each sum with its interventions" we enumerate all possible interventions (and resulting values) and increment each sum that includes the intervention. Thereby, rather than storing the functions and interventions, we only need to store and update the value of the sums.
By definition, each sum Ey, P((a))))) the input can be written as Σn Pu Ey (m.] 1, where the second sum does not depend on Pu- As in Lemma 12 one can write the probabilities as a single vector Pu. each sum
row in matri A, such that entry of the row is if F. u += [ag]6 holds and otherwise. Then one obtains the value of all sums as product Apu A
For example, sum like E. P([X=>]Y=y) performs multiple interventions on X, which is difficult to evaluate. Sums containing only single intervention could he evaluated trivially.
14

---

Published as a conference paper at ICLR 2025
Input: SAT instance
Output: Is the instance satisfiable?
Guess small model probabilities Pui
Guess a causal order XI...,,
Rewrite each sum Σy. P((a:]6,) in the imput as Σu Pa Ly.:F,u 1;
Initialize counter to zero for each such sum for Pu 0 do
Guess values Ti, I1, Simulate-Interveniions(L] 0, (1,
end
Replace the sums by & and verify whether the (in-)equalities are satisfied;
10
Function Simulate- Simulate-Innerventtinn Interventions(i, a, Z1...., In)
Input: Current variable X,; set of interventions a; values Ti. 2i....,2n if n. then
II
for each counter Cj do for all possible values yj of the sum do
13
if a (after inserting y:) XX; 2; for oil and 21 Z1rm satisfy 8, (after
inserting y;) then increment Cy by Pu
end
17
end
18
end
19
else
+ Or, 21, ...,...
21
for value v do
Let 1 2 F1, .... Ini
23
x = v:
u + then
25
guess new values 14,, 3/
26
end Gimulate-Intervention + 1, (i] 2i
end
29 end
Algorithm 1: Solving Ba(()))) Cz
small model property &l follows that there are only polynomial many, rational probabilities Pu. These can be guessed non non-deterministicall..
Next, we combine the terms En Pu of all sums (implicitly). For example, two sums Ey. P((a.6))) Ey; ()(()) can be rewritten as
Σ P((a(66)) + +I P((a,10,)= = y1
=Pr Pu
Σ
I+ u
1+
Pu
Σ
1
y,
y5 uF jayl6;
Σ
1+ yyFF.u [os]4
Σ
yaF (a:36
'Small model property means that whenever there is a satisfying probability distribution, then there is also with only polynomially many positive elementary probabilities. Note that, e.g., the probability distribution n binary random variables has 2n entries. Some of the previous results refer eagin al.) 1990);;
lbeling leard (2020), are hased on small property.
The algorithm just guesses them without doing any rewriting of the equations. This paragraph just explains why this guessing is possible.
15

---

Published as a conference paper at ICLR 2025
The algorithm performs this sum u in line 3 and calculates the next sums in the subfunction. We can and will ignore the actual values u. Relevant is only that the value of the sums is multiplied by Pu and that the functions F might change in each iteration.
Recall that the functions = (Fi, , Fn) determine the values of the endogenous variables, that is the value of variable X; is given by x; (u, .1,-... 11 Thereby the functions (i.e. variables) have a causal order X1 < x Xn, such that the value I; only depends on variables X, with j < i. In reverse, this means that each intervention on variable X; can only change variables X3 with j > i.
Rather than storing the functions J = (Fi, Fn), the algorithm only stores the values x; F [u, .1....,I--1)) i.c. the values of the endogenous variables. The algorithm knows these values as well the causal order, since they can be guessed non non-deterministically..
The subfunction Simulate-Intervention then performs all possible interventions recursively, interven- ing first on variable X1, then X2, ... until X,, The parameter means an intervention on variable X,, a is the set of all previous interventions, and 21...., In the current values.
In line 20 proceeds to the next variable, without changing the current variable X; (simulating all possible interventions includes intervening on only subset of variables). In line 21 it enumerates all values x for variable X,- If x; = xy then the intervention does nothing. x, * n/. then the intervention might change all variables X,, with j > i (because the function Fj, might depend on X; and change its value). This is simulated by guessing the new values z'j. Thereby, we get the new values without considering the functions.
In the last call, line 27 it has completed a set of interventions a. The function then searches every occurrence of the interventions in the (implicitly expanded) input formula. That is, for each sum (4 1, counts how often aj = a occurs in the sum while the values 2, satisfy dy.
Since each intervention is enumerated only once, in the end, it obtains for all sums their exact value. It can then verify whether the values satisfy the (in-)equalities of the input.
If a satisfying model exists, the algorithm confirms it, since it can guess the probabilities and the values of the functions. In reverse, if the algorithm returns true, satisfying model can be constructed. The probabilities directly give a probability distribution P(u). The functions F' can be constructed because, for each set of values u, .1,,,..,,,;44 only single value for x, is guessed, which becomes the value of the function.
Algorithm I runs in non-deterministic polynomial space and thus in PSPACE.
A.3 PROOFS SECTION 3,3
Proof of Theorem The problem can be solved in NEXP because expanding all sums of SATZ, (in)s) instance creates a SATE; instance of exponential size, which can be solved non-detemministically in a time polynomial to the expanded size as shown by Mossé al. (2022).
To prove hardness, we will reduce the satisfiability of a meniönfinkel-Bermaa sentence to the satisfiabil- sentences (also called Effectively Propositional
ity of SAT (z) The class of Schönfinkel Logic, EPR) is a fragment of first-order logic formulas where satisfiability is decidable. Each sentence in the class is of the form YxVyd whereby e can contain logical operations A, V, 7, variables and y, equalities, and relations (x. y) which depend on a set of variables, but t cannot contain any quantifier or functions. Determining whether a tetööniinke-Beemaan sentence is satisfiable is an NEXP-complete problem Lewis 1980) even if all variables are restricted to binary values Achilleos (2015).
We will represent Boolean values as the value of the random variables, with 0 meaning FALSE and 1 meaning TRUE. We will assume that c 2, so that all random variables are binary, i.c. Val {0. 1}.
In the proof, we will write (in)equalities between random variables as = and f. In the binary setting, X Y is an abbreviation for (X = 0 Y 0) v (X LAY =1). and X o Y an abbreviation
Rather than incrementing the counter ej by 1 and then multiplying the final result by Pa, we increment it directly by Pu-
16

---

Published as a conference paper at ICLR 2025
for for -). To abbreviate interventions, will write [w] for [W = w/, [w] for interventions multiple variables !W= = w|. and [v w| for interventions on all endogenous variables except W.
We use random variables X {Xi.... Xn) and Y (Yi.....,, Yn for the quantified Boolean variables x, y in the sentence Exvyy. For each distinct k-ary relation (2(21,..... 2x) in the formula, we define random variable RG and variables Z ................................ of that relation Ri(ti...... .... (tt)) with t E (-1..... nn ...... UnJ. we define another random variable R.
......, Z for the arguments. For the j-th occurrence
We the following constraint to ensure that R₂ only depends on its arguments:
Σ P(2 ................................ 2R + (.) I
(6)
Thereby Ev refers to summing over all values of endogenous variables" in the model and constraint says that an intervention on Z,, Z gives the same result for Rs as an intervention on 2,,..., z and the remaining variables, excluding R..
We use the following constraint to ensure that R& only depends on its arguments:
P(U P( G + \
(7)
and that Ri and R; have equal value for equal arguments:
Σ -(
- * 12,=t
2 -
(8)
We add the following constraint for each X, ensure that the values of X are not affected by the values of Y:
ΣΣ P(V \ x A [v (xi,)), Y=y =0
Here the first sum sums over all values of all endogenous variables V (including X; and Y), and the second sums sums over values for variables Y. The intervention [v xy] intervenes on all variables except X, and sets the values y to the values of the first sum. The intervention [v y), Y y'] intervenes on all variables except X; and sets the values y to the values y' of the second sum. The constraint thus ensures that the value of X, does not change when changing Y from y to y
Let & be obtained from eb by replacing equality and relations on the Boolean values with the corresponding definitions for the random variables:
Σ F(rlw)) 2
(10)
Suppose the SAT base(z) Ca instance is satisfied by model DI. We need to show 3xVyd is satisfiable. Each probability P(..) implicitly sums over all possible values u of the exogenous variables. The values x the variables X might change together with the values u, however, any values x that are taken at least once can be used to satisfy ExVy;; If there was any x that would not satisfy for all values of y. P([jje (²) would be less than for these values of x (determined by u) and y. and equation (TO) would not be satisfied.
For each relation R;, we choose the values given by the random variable R₁- Each occurrence R2 (L,),...,(")) ,,,)) has a value that is given by [ = .l.....
... 2 1 R. in the model Dt. Due to equations (8 and equations (7). that the same value as [T! tly.........................tt Th t 1,) which the value used in [y] Since yTu is satisfied, so is & and Exkyy,
lI All variables include variables 2,,...,
17

---

Published as a conference paper at ICLR 2025
Suppose Exvyy' is satisfiable. We create deterministic model Di as follows: The value of random variables X is set to the values chosen by 3x. The relation random variables R; are functions depend- ing random variables Z!..... Z that return the value of the relation . Zk.). The relation random variables R on arguments ....... ................................
T. return the value of the relation R, (tig....... +.t)) This satisfies Equation 6 and 7 because the functions only depend on their arguments, and Equation because the functions result from the same relation (so the functions are dependent, but causally independent, which yields a non-faithful model. But the equations do not test for faithfulness or dependences). All other random variables can be kept constant, which satisfies Equation (dustton@(desppie be- ing constant in the model, the causal interventions can still change their values). Finally, Equation I0 holds, because v is satisfied for all Y.
A.4 PROOFS OF SECTION
Mossé al. 2022 already prove SAT ER when the - allowed neither contain subtractions nor conditional probabilities. We slightly strengthen this result to allow both of them.
Lemma 15. SAT JR. This also holds true if we allow the basic terms to contain conditional probabilities.
2022) show that SAT Es without subtraction or conditional probabilities is in ER. Their algorithm is given in the form of a NP-reduction from SAT to ETR and using the
Proof. (Mossé et al.
closure of FR under NP-reductions. In particular given a 4g -formula yp, they replace each event P(c) by the sum Σee :8 (6()) where A+ C &counterfact is a subset of size at most [yp]. They add the constraint S P(5) and then replace each of the PP()) by a variable constrained to be between and to obtain a E-Tffforula. Note that the final ETR-formula allows for subtraction, so oo allowed to have subtractions as well. Remains show how to deal with conditional probabílities, We define conditional probabilities (6]88) to be undefined if (8") = O (this proof works similarly for other definitions). yp replace P(8)8') by P(á,8"),
P(8") The resulting ETR-formula then contains some divisions. To remove some division z we use Tseitin's 's trick and replace 3 by a fresh variable z. We then add the constraints a = = 33 and 3 f 0 to the formula.
Now are ready to show that SAT can be solved in NEXP the Reals.
Proof of Theorem T0 By Lemma 15 we know that SAT is in ER. Thus, by (Erickson et al. 2022 there exists an NP real algorithm, call it A, which for given Cgoh -formfoomulaa decides is satisfiable.
Es To solve the Sar (x) problem, NEXP real algorithm expands firstly all sums of given instance
and creates equivalent SAT instance of size bounded exponentially in the size of the initial input formula. Next, the algorithm A is used to decide if the expanded instance is satisfiable.
18

---

Published as a conference paper at ICLR 2025
B LEVELS OF PEARL'S CAUSAL HIERARCHY: AN EXAMPLE
To illustrate the main ideas behind the causality notions, we present in this section an example that, we hope, will make it easier to understand the formal definitions. In the example, we consider a (hypothetical) scenario involving three attributes represented by binary random variables: pneumonia modeled by Z = 1, drug treatment (e.g., with antibiotics) represented by X = 1, and recovery, with == 1 (and Y 0 meaning mortality). Below we describe an SCM which models an unobserved true mechanism behind this setting and the canonical patterns of reasoning that can be expressed at appropriate layers of the hierarchy.
Structural Causal Model An SCM is defined a tuple (F.P. U, which is of umobserved nature from the perspective of researcher who studies the scenario. The SCM models the ground truth for the distribution P(U) of the population and the mechanism F. our example, the model assumes three indepen- dent binary random variables U = LU, U2, Uz}. with probabilities: P(U1=1) = 0.75, 1() = 0.8, P(U;=1) = 0.4, and specifies the mechanism F = (Fi F2, F3} for the evaluation of the three endogenous (observed) random variables Z, X,Y Y as follows:
U1 U2
U3
P(u)
Z
X
Y
0
0
0.03
0
0
0
0.02
0
1
0
0.12
0
0
0
1
1
0.08
0
1
0
0
0.09
0
0
0
0
0.06
0
0.36
1
0
1
1
0.24
0
Z = (U;) 1- X == (2, U2) = (1- D2)
F3 U1, U3) (011-(()11100))0
(1=) Ug. Thus, our model determines the distribution P(u). for u = (u1, U2, Uz). and the values for the observed variables, can be seen above.
The unobserved random variable U1 models all circumstances that lead to pneumonia and Z is function of U, (which may be more complex in real scenarios). Getting treatment depends on having pneumonia but also on other circumstances, like having similar symptoms due to other diseases, and this is modeled by U2. So X is a function of Z and U2. Finally, mortality depends on all circumstances that lead to pneumonia, getting the treatment, and on further circumstances like having other diseases, which are modeled by U3. So Y is function of U1, X, and U3. We always assume that the dependency graph of the SCM is acyclic. This property is also called semi semi-Markovian.
Layer Empirical sciences rely heavily on the use of observed data, which are typically represented as probability distributions over observed (measur- able) variables. In our example, this is the distribution P over Z, X, and
X Y
P(z, x,, y)
0
0.09
0 0
0.06
Y. The remaining variables U1. Uz Us. as well the mechanism F, are of unobserved nature. Thus, in our scenario, researcher gets the probabilities (shown to the right) P(2, y) = En, 6z, y) P(u), where vectors 1f
0 1
0
0.36
1
0.24
0
0.15
u (u,, U2, Uz) E 13 and (2, ( [2(z, =2, and (2, u1, u2)=y;; otherwise 67, 07, = 0. The relevant query in our scenario P(Y=1|X==1 can be evaluated as P(Y=1|X=1) = X(I=I,X=I)PP(X 0.24/0.6 = 0.4 which says that the probability for recovery (Y=1) is only 40% given that the patient took the drug (X=1). On the other hand, the query for X=0 can be evaluated as P(Y==1X00) = X opinion that the drug is irrelevant to recovery.
0
0.10
= 0.16/0.4 0.4 which may lead to the (wrong, see the next layer)
Consider a randomized drug trial in which each patient receives treat-
Layer 2
U1 U2
U3
P(u)
Z
X=1Y
0
0.03
1
I
of pneumonia (Z) and other conditions
ment, denoted as do(X-=1), regardless
0 1
0 0
0.12
0.02
1
1
1
1
0
Z
Y
P([X=
112,,))
(U2). We model this by performing a hypothetical intervention in which we re- place in F the mechanism F2(Z, U2) by the constant function 1 and leaving the remaining functions unchanged. FI denotes the new mechanism, then the post-inteerventionll dis-
1
0.08
1
0
0 0
0.45
0.30
0
0.09
0
0.06
0
1
1
101
0.10
1
0.36
0
1
0
1
0.15
1
0.24
0
1
1
If Fx=1 =
tribution P([X=1]Z,Y) is specified as P([X=1]2,y) - E2..8 (22 P((u), where 85 denotes function 5 above, but for the mechanism Fx=1 (the distribution is shown on the right-hand side). A common and popular notation for the post-interventional probability is P(Z, (]do(x=1)) In this paper,
the notation P([X=1] Z, Y) since it is more convenient
19

---

Published as a conference paper at ICLR 2025
for analyses involving counterfactuals. To determine the causal effect of the drug recovery, compute, in an analogous way, the distribution P[[X=0] Y) after the intervention do which means that all patients receive placebo. Then, comparing the value P([X=1|==1) =1) 0.45 P([x=0]y==) > 0. This can be interpreted as a positive (average) effect of the drug in the population which is in opposite to what has been inferred using the purely probabilistic reasoning of Layer 1. Note that it is not obvious how compute the postiinterventional distributions from the observed probability P(Z,X, Y); Indeed, this is challenging task in the field of causality.
with 0({x=0)==1) = 0.40, we can conclude that P([x=1J==1)
Layer 3 The key phenomena that can be modeled and analyzed at this level are counterfactual situations. Imagine, e.g., our scenario there is group of patients who did not receive the treatment and died (X -0, 00). One may ask, what would be the outcome Y had they been given the treatment (X-1). In particular, one can ask what is the probability recovery if we had given the treatment to the patients of this group. Using the formalism of Layer 3, we can express this as a counterfactual query: P Y=0) = P( 0) incorporates simultaneousyy two counterfactual mechanisms: Fx=1 and F. This is the key difference to Layer 2, where we can only have one. We define the probability in this situation follows:
(( Y=0). Note that
the event X (Y=)
P([X=a](Z=2, Y=y) (Z==', X- E. 65x (2, v) 8F,u(=', //,//) P(u).
X=0, Y= is satisfied only for (U1, U2 U2) (00,0,0, (0. 1, 1,0), (1,0, 0)) (first table), and of them only { 0), (0. P((X-i)y-|X--0, Y-0) 1.0} satisfies [X=1|y=1 (third table). Thus, by marginalizing Z, we get 0.15/0.24 = 0.625 which may be interpreted that more than 62% of patients who did not receive treatment and died would have survived with treatment. Finally, we would like to note that, in general, the events of Layer simultaneously many counterfactual worlds.
be quite involved and incorporate
Graph Structure of an SCM Below we remind, how an SCM can be represented in the form of a Directed Acyclic Graph (DAG) and show such a DAG for the model discussed above.
Let 2T = (F = {Fi. F.).P, U, = i X, ) be an SCM. We assume that the model is Markovian, i.e. that the exogenous arguments U., U, of F,, resp. F, are independent whenever i j. These exogenous arguments are not shown in the DAG. We note that general model as discussed above, called semi-Markovvan, which allows for the sharing of exogenous arguments and allows for arbitrary dependencies among the exogenous variables, can be reduced in a standard way to the Markovian model by introducing auxiliary "unobserved" variables. Thus, in our example, to get Markovian model, we can assume, X = {x,Y Y, U1}. where X, Y, Z remain observed variables but U, is of unobserved nature.
We define that DAG g (X, E) represents the graph structure of 21 if, for every Xj appearing as an argument of F,, X; + X, is an edge in E. DAG G is called the causal diagram of the model D1 Pearl (2009); Bareinboim et al. (2022). The DAG for the discussed SCM therefore has the following form (here, as is usually done in Markovian models, variables U2 and U3 that only affect X, respectively Y, are omitted):
Z K
U
Moreover, the DAG of the intervention model discussed in subsection Layer 2, with functional mechanism Fx=1 has the following form, meaning that all in in-going edges X are removed from the pre-interventional model:
2 K U
Y
20

---

Published as a conference paper at ICLR 2025
C SYNTAX AND SEMANTICS OF THE LANGUAGES OF THE PCH: FORMAL DEFINITIONS
We always consider discrete distributions in the probabilistic and causal languages studied in this paper. We represent the values of the random variables as Val = {0. 1..... C - 1 and denote by X the set of random variables used in a system. By capital letters X1, X2..... we denote the individual variables and assume, w.l.o.g., that they all share the same domain Val. A value of X; is often denoted by xę or a natural number. this section, we describe syntax and semantics of the languages starting with probabilistic ones and then we provide extensions to the causal systems.
By an atomic event, we mean an event of the form X = I, where X is a random variable and is value in the domain of X. The language Epop of propositional formulas over atomic events is defined as the closure of such events under the Boolean operators A and -. To specify the syntax of interventional and counterfactual events define the intervention and extend the syntax of Epop to Epon-int int and Ccomntefaac, respectively, using the following grammars:
Eprop is defined by
p ::= X = 2 -p P pAp
Ein is defined by
i : T|x=z
Epost-ine is defined by
pi := [i]p
Ecounterfact is defined by == Pi cccc
Note that since T means that no intervention has been applied, we can assume that Epmp C &pont-inn-
The PCH consists of three languages L1; L2, La, each of which is based on terms of the form P(8). For the (observational or associational) language Ct, we have ō E Eprop. for the (interventional) language L2, we have ó E Epost-int and for the (counterfactual) language C3. ô E Ecomnterfact- The expressive power and computational complexity properties of the languages depend largely on the operations that we are allowed to apply to the basic terms. Allowing gradually more complex operators, we describe the languages which are the subject of our studies below. We start with the description of the languages T," of terms, with i 1,2, 3, using the following grammar [2]
Thuuse
t ::= P();)
T Thae((
t :: P((:)) Σn t
Tfll t ::: P();) t+t
t ::: PP():) t t Σ,
T,maly :::= P().) t + -t
t ::= P(())) |++t -t t E
where 61 are formulas in Eprop. 8g Eposttinns 83 E Econmterfact-
The probabilities of the form P())) are called primitives or basic terms. In the summation operator Σ we have dummy variable z which ranges over all values 0, 1...., c- The summation Σ, is purely syntactical concept which represents the sum +(%=+)+ +t 1/4). where by t t("/n), we mean the expression in which all occurrences of x are replaced with value u. For example, for Val {0, 1). the expression>> PPY=1, X =x) semantically represents P(Y=1,, =yy=,, X 0) + X-, We note that the dummy variable æ is not a (random) variable in the usual sense and that its scope is defined in the standard way.
In the table above, the terms in Thoas are just basic probabilities with the events given by the corresponding languages Eprops Epost-int- or Ecounterfact. Next, we extend terms by being able to compute sums of probabilities and by adding the same term several times, we also allow for weighted sums with weights given in unary. Note that this is enough to state all our hardness results. All matching upper bounds also work when we allow for explicit weights given in binary. In the case of T, we are allowed to build polynomial terms in the primitives. On the right- hand side of the table, we have the same three kinds of terms, but to each of them, we add a marginalization operator as a building block.
The polynomial calculus 7.Poly was originally introduced by Fagin, Halpern, and Megiddo (Fagin et al. 1990) (for i = 1) to be able to express conditional probabilities by clearing denominators. While this works for T.oaly this does not work in the case of T. (2)) since clearing denominators
In the given grammars omit the brackets for readability, hut assume that they can be used in standard way.
21

---

Published as a conference paper at ICLR 2025
with exponential sums creates expressions that are too large. But we could introduce basic terms of the form (6), with 5 E Eprop explicitly. All our hardness proofs work without conditional probabilities but all our matching upper bounds are still true with explicit conditional probabilities. Expression (P -
-3) a valid term in 7i and > IP[[X (01 Z-=))
and (((=--0))))) 2= are valid terms in the language T: (19) for example.
Now, let Lab = {base, base lin, lin poly, poly(E)) denote the labels of all variants of lan- guages. Then for each E Lab and i = 2, 3 we define the languages L of Boolean combinations of inequalities in a standard way:
C is defined by f ::= If where t, t' are terms in T
Although the language and its operations can appear rather restricted, all the usual elements of probabilistic and causal formulas can be encoded. Namely, equality is encoded as greater-or- equal in both directions. e.g. P(x) = P(y) means P(x) > P(v) A P(v)= 2 P(z). The number 0 can be encoded as an inconsistent probability, i.e., P(X=1 A X-2). In a language allowing addition and multiplication, any positive integer be easily encoded from the fact IP(T) = 1, e.g. 4 = (1 + 1)(1+ + 1) = (P((T) + (P())) P(T).. If a language does not allow multiplication, one can show that the encoding is still possible. Note that these encodings barely change the size of the expressions, so allowing or disallowing these additional operators does not affect any complexity results involving these expressions.
To define the semantics of the languages, we use a structural causal model (SCM) as in (Pearl 2009 Sec. 3.2). An SCM is tuple M8 (F, P. U, X), such that V = =UUX is a set of variables partitioned into exogenous (unobserved) variables U- = [U1, U2.... and endogenous variables X. The tuple F == (Fi,... ] consists of functions such that function F; calculates the value of variable X, from the values (x, u) of other variables in V as (pa,, u,)
13 where Pa, C X and U; C U. P specifies a probability distribution of all exogenous variables U. Since variables X depend deterministically on the exogenous variables via functions F,, F and P obviously define the joint probability distribution of X. Throughout this paper, we assume that domains of endogenous variables X are discrete and finite. In this setting, exogenous variables U could take values in any domains, including infinite and continuous ones. A recent paper (Zhang et al. 2022) shows, however, that any SCM over discrete endogenous variables is equivalent for evaluating post-interventional probabilities to SCM where all exogenous variables are discrete with finite domains. As a consequence, throughout this paper, we assume that domains of exogenous variables U are discrete and finite, too.
For any basic formfulmula x,= (which, in our notation, means do(X,=I;)) we denote by Fx,=z, the function obtained from by replacing F; with the constant function Fi(v) == Ig. We generalize this definition for any interventions specified by a E Emt in a natural way and denote as F. the resulting functions. For any şp E Epmp: we write F, u }= yp yp is satisfied for values of X calculated from the values u. For a E Eis, we write F, F= [alsp if Fa. u } p. And for all vb, 1/1 4/2 E Commterforr we write (i) F,u F= up if F,u u j db and (ii) F, u } th A th2 F, u }= t1 and F, F,u. F th2. Finally, for th E Ecounterfact. let Son {u F, } v}. We define [e]sm, for some expression e, recursively in a natural way, starting with basic terms as follows [T) = EueSon(s) P(u) and, for 8 Epop- [P(*)))]Tn [TP(bb A 8)]lx/ [PP))//(())] assuming that the expression is undefined if [IP())]
O. For two expressions e and e2, we define M F= I 02, if and only if, [ei]oR I [[ez]en The semantics for negation and conjunction are defined in the usual way, giving the semantics for Mi F= o for any formula y in Lz.
Be consider recursive models, that is, we assume the endogenous variables are ordered such that variable X, (i.c. function F.) is not affected by any X, with > i.
22


Reviews:
[{"review_id": "1QCznFXxbo", "reviewer": "Reviewer_enRi", "summary": "The paper studies the computational complexity of the satisfiability problems of queries under different causal layers. In particular, it considers queries that may involve marginalizations ($\\sum$) and proves that the sat problems with basic and linear terms under L1, L2, L3 layers belong to the complexity classes of $NP^{PP}$, PSPACE, and NEXP. Moreover, it completes the open problem in Van der Zander et al. to show that the sat problem with polynomial term under L3 also belongs to succ-$\\exists R$.", "questions": "1. Are there any (potential) applications of the satisfiability problems mentioned in this work? For example, do they have any implications in causal identifiability or causal discovery (structure learning)? I can see the applications of the validity problems but not sure about the satisfiability problems.\n2. Why/when do queries with marginalization become important? How does this relate to existing works on marginalizing (forgetting) variables from causal models?\n3. In Appendix A.2 proof of Lemma 14: \"A small model property follows that there are only polynomial many, rational probabilities $p_u$\" I don’t know what \"small model property\" is.\n\nMinor typos:\n- Line 816: \"the second sums\" -> \"the second sum\"\n- Line 863: \"$\\frac{P(\\delta)}{P(\\delta')}$\" -> \"$\\frac{P(\\delta)}{P(\\delta, \\delta')}$\", maybe?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I checked the proofs and most of them make sense to me. The proofs are also quite rigorous in my opinion.\n- The paper is succinct and clearly structured. \n- The results are novel and are important contributions to the complexity of casual satisfiability problems.", "weaknesses": "I think the main challenge is for the readers to process the complexity results.\n\nHere are some suggestions:\n1. I think providing more background on the complexity classes in the preliminaries section can be very helpful. Currently the paper points to [Arora & Barak 2009] textbook for more background about the complexity classes. If the page limit permits, it's better to summarize the definitions for each complexity class considered in this paper along with some complete problems in each class. This should make the paper more self-contained.\n2. A lot of contents in Appendix C should be moved to Section 2.1. For example, I got lost in the definitions of base, lin, and poly, etc.. Also, please provide some concrete examples so that we know immediately their differences.\n3. I think it is worth stressing that the satisfiability problem does not assume anything about SCMs, nor does the causal structure. In the classical work on the complexity of probabilistic inference, it is often assumed that both the structure and parameterizations are known (Remark 5 in the paper). In causal effect identification, the causal structure (graph) is often assumed to be known.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tk7YzJil0H", "reviewer": "Reviewer_cUWX", "summary": "This paper studies the complexity issues of the satisfiability and validity problems of formulas and shows an increasing complexity within the framework of Pearl’s Causal Hierarchy of reasoning: observational, interventional and counterfactual.", "questions": "(1)There are several operations in the structure: sum, marginalization, conditioning. What are their roles in the increasing complexities of the hierarchy?\n(1)Could you give nontrivial examples to demonstrate different levels of reasoning and to illustrate the corresponding increasing complexities?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "(1)The paper studies an important theoretical problem for causal reasoning and answers some open problems in this field. \n(2)The paper provides a good motivation and detailed literature.", "weaknesses": "(1)The paper is very technical, condensed and very hard to understand. Hence it is difficult to check the mathematical soundness and evaluate the contributions. But the mathematical proofs turns out to more important than anything else including originality and insights in this paper. The main text consists of a list of theoretical results. The topic is also very limited. Since the paper is mainly about the pure complexity results, probably it is more appropriate as a journal submission or a pure theory conference.   \n(2)Some important results in the paper are related to some uncommon complexity classes like succ-ExistentialR-completeness. The paper fails to provide a clear explanation of this class and some motivation of the relationship. \n(3)There is no a concrete example which demonstrates the increasing complexity results. Such an example would help understand the motivation behind the complexity results for different levels of languages.\n(4)The introduction in Section 2.1 of Pearl’s PCH is very messy. It would take some hard time to understand the main components and the structure of the hierarchy.  It would be better to illustrate the graph structures of SCMs and give some examples to illustrate the increasing structures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pxkGmD5JR2", "reviewer": "Reviewer_J9DB", "summary": "The paper studies the complexity of the satisfiability problem of various logics for describing properties of structural causal models. The logics incorporate probability comparisons of statements including interventional counterfactuals. The authors give a very rigorous study on the complexity of the satisfiability problem of fragments of the logics they consider.", "questions": "None.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very rigorous, and the results are surely interesting for the community of researcher working on logics for causal reasoning.", "weaknesses": "While the call for papers mentions causal reasoning as one of it's topics knowing, I do not think that a paper whose main contributions are pure complexity results for logics for causal reasoning is suitable for ICLR. Though the precise complexity results obtained might have some impact on the algorithmic aspects of causal reasoning. The paper is an almost pure logic paper studying computational complexity landscape of the logic they consider and as such is a valuable contribution that should be carefully reviewed and published in a more suitable venue. I would urge the authors to resubmit the paper to a venue that can better appreciate the results There are numerous conferences of this kind, including A* conferences such as LICS and KR, but also JELIA, CSL, and many other.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BESGr8GW5p", "reviewer": "Reviewer_K9we", "summary": "This paper studies the complexity of satisfiability in three increasingly complex probabilistic frameworks: purely probabilistic, interventional, and counterfactional. They build on previous work which does not allow for marginalisation, and the authors add results that allow for marginalisation.\nTheir findings are interesting: for each of the three frameworks, they find to which complexity class it belongs, and interestingly the three classes differ (under widely accepted assumptions).\nThe authors motive their approach well, and cite the relevant literature, at least so far as I can see. The paper gives proofs for all the claimes in an appendix, so the findings are well supported.\nThis paper adds to the field of causality in probability theory, which is becoming increasingly more relevant, with new results that have the potential to influence further studies in this field.", "questions": "Here are three questions that would increase the readibility in my opinion:\n1. Page 4, line 182: The basic term P( [ X_1=x_1] X_2=x_2 ) does not belong to T_1^base, if I understand it correctly. The way it's written now, seems to suggest that it does. Please clarify this.\n2. Page 6, line 289: What does it mean for a sum to be \"equivalent\" to another sum? Does the author(s) mean \"equal\"?\n3. Theorem 9: The proof idea only seems to (informally, but I like this here, as I mentioned in the \"strengths\" section) show that the satisfiability problems are NEXP-hard instead of NEXP-complete. The proof in the appendix does, however, prove the desired result. I suggest that the authors rephrase this, or (if I'm mistaken here) explain why the current proof idea (informally) shows that they are NEXP-complete.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "In my opinion, this paper studies a very relevant question, which naturally arise. The current interest in causality in probability theory makes this paper even more relevant. The results obtained are important on its own right, and may well influence further research.\n\nThis paper is well written. The authors took great care in explaining the concepts, and generally succeeded with this (but not everywhere in their paper – see my \"questions\" section).\n\nOne particular thing I appreciated, was the use of 'proof ideas'. In my opinion, this is great to convey the idea, at the same time reducing the risk that the reader loses themselves in details. This seems a nice way for conferences, to my taste.\n\nIn all, I am very positive about this paper. I identify later a small number of points where minor improvements are possible. Note that this field is not my expertise, so while I am rather confident that this is a good paper, I am open to arguments against this.", "weaknesses": "In general, I am positive about this paper, and I only identify a small number of weaknesses.\n\nWhile the authors generally motivate their approach, and introduce the necessary concepts, well, at some points there is improvement possible. \n- For instance, in Table 1 the authors should make more clear that the languages L1, L2 and L3 refer to their introduction on the next page in Section 2.1. The authors do not refer there to L1, L2, and L3, which makes it more harder to make this link.\n- An instance where the motivation could be improved, is Section 3, the sentences following that of Equation (3). There, the authors remark that adding marginalisation to a language does not change the expressivenes of it. It comes to wonder, then, why the authors are particularly interested in the questions they answer: if adding marginalisation does not change the expressivenes, why is it important to add this? The authors expand a bit on this in the Introduction, but I would rephrase the sentence here, or expand on it, in order to make the paper feel better motivated.\nAlso, how do we know that adding marginalisation to a language does not change the expressivenes of it? It may be a well known fact, but I would add a reference.\n\nI end this section with a small list of small remarks and typos:\n- Abstract, last sentence: Please be more specific about which open problem in which field. Ideally, give a reference that states that the problem you describe is open.\n- Page 2, line 065: add a space between \"see, e.g.,\" and \"(Pearl, 1988;\".\n- Page 6, line 314:  I would write that the sum \"ranges\" over all values, instead of \"sums\" over it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)