Probabilistic and Causal Satisfiability:
Constraining the Model

One starting point for our investigations is a pioneering paper work by Fagin et al. [11], who introduce a logic to reason about probabilities. We are given a set of random variables over some fixed finite domain $D$, often $\{0,1\}$. They consider formulas consisting of Boolean combinations of (in)equalities of basic and linear terms, like $\mathbb{P}((X=0\vee Y=1)\wedge (X=0\vee Y=0))=1\wedge (\mathbb{P}(X=0)=0\vee \mathbb{P}(X=0)=1)\wedge (\mathbb{P}(Y=0)=0\vee \mathbb{P}(Y=0)=1)$ with binary variables $X,Y$. The authors provide a complete axiomatization for the used logic, which is essentially a formalization of Nilsson’s probabilistic logic [24] and they show that the problem of deciding satisfiability is $\mathrm{𝖭𝖯}$-complete. Thus, surprisingly, the complexity is no worse than that of propositional logic. Fagin et al. extend then the language to (in)equalities of polynomial terms, with the goal of reasoning about conditional probabilities. They prove that the latter variant is $\mathrm{𝖭𝖯}$-hard and contained in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. Recently, Mossé et al. [22] have given the exact complexity of this problem, showing that deciding the satisfiability is $\exists ℝ$-complete, where $\exists ℝ$ is the well-studied class defined as the closure of the Existential Theory of the Reals (ETR) under polynomial time many-one reductions.

In this work, we study the satisfiability (and validity) problem for such formulas involving probabilities. As already seen above, the choice of the admissible operations have an impact on the complexity. There are further choices, which we can make and which we will discuss in the following. All these choices have an impact on the complexity. Therefore, we will phrase these satisfiability problems as multi-parametric or multi-dimensional problems. The first dimension is the expressiveness of the underlying arithmetic:

$\bullet$ Arithmetic:

Basic, linear, or polynomial.

The second dimension will be the layer in the Pearl’s Causal Hierarchy which we have already discussed in the previous section. Reasoning about uncertainty has been the subject of intensive studies in the past decades. The research has resulted in a large number of significant achievements, especially in the case of probabilistic inference with the input probability distributions encoded by Bayesian networks [26]. The setting is of great interest in AI since it allows one not only to reason about observations, but also about causality, and even counterfactuals, which is for instance important in fairness considerations. These three layers form a hierarchy of increasing expressiveness (for a more detailed description of the concepts, see Section 2).

$\bullet$ PCH layer:

Probabilistic (observational), causal (interventional), or counterfactual.

The languages used in [11, 22] are capable of fully expressing probabilistic reasoning, in particular, they allow to express marginalization, which is a common paradigm in this field. However, in the frameworks discussed above, this ability is very limited since the languages do not allow the use of a unary summation operator $\mathrm{\Sigma }$. Thus, for instance³³3 We have chosen this example because it is short. In this particular example, the joint probability could be directly written as $\mathbb{P}(y)$ in the calculus of Fagin et al., see the formal definition in Section 2. This is however not true anymore if we sum over more complicated expressions., to express the marginal distribution of a random variable $Y$ over a subset of (binary) variables $\{Z_1,\mathrm{\dots },Z_m\}$ as ${\sum }_{z_1,\mathrm{\dots },z_m}\mathbb{P}(y,z_1,\mathrm{\dots },z_m)$, an encoding without summation requires an expansion into $\mathbb{P}(y,Z_1=0,\mathrm{\dots },Z_m=0)+\mathrm{\dots }+\mathbb{P}(y,Z_1=1,\mathrm{\dots },Z_m=1)$, which of exponential size in $m$. Consequently, to analyze the complexity aspects of the studied problems, languages that exploit the standard notation of probability theory and statistics, one requires an encoding that represents marginalization via the sum operator $\mathrm{\Sigma }$. In the recent paper [38], the authors present the first systematic study in this setting. They introduce a new natural class, named $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$, which can be viewed as a succinct variant of $\exists ℝ$.

Given the impact of the compact marginalization operator, the way we can perform marginalization will be the third dimension:

$\bullet$ Marginalization:

Expanded or compact.

For expanded marginalization, the complexity results by Fagin et al. [11], as well as Mossé [22] et al., can be easily adapted to capture all other parameter ranges, see the full version of our work. Therefore, throughout this paper, we only deal with the case when we have a compact marginalization operator in our calculus.

The fact that the decision problem for basic and linear arithmetic without summation is in $\mathrm{𝖭𝖯}$ is not obvious. A model for a formula is a joint probability distribution of $n$, say, binary variables, which is a table with $2^n$ entries. Furthermore, it is a priori not clear that the bit size of the entries is polynomial. It turns out, that these problems have what is called a small model property. If there is a model, that is, a joint probability distribution satisfying the expression, then there is one which has only polynomially many non-zero entries. This follows by linear algebra arguments. If the model is small, then it can be guessed efficiently in $\mathrm{𝖭𝖯}$. In the case of polynomial arithmetic, we still have the small model property, but one cannot guarantee that the entries have polynomial size. However, the compact marginalization operator destroys the small model property that was crucial in the work of [11] and [22] and in fact increases the complexity of the satisfiability problems dramatically [38]. So the next dimension is the model size, which can either be polynomially bounded or arbitrary:

$\bullet$ Model size:

Small (polynomially many entries) or unbounded.

The impact of restricting the model size in the presence of a compact marginalization operator will be one of the main topics in this work (see the results in Section 5).

Causal models are often represented as a graph or Bayesian network where all random variables are represented as nodes and the edges encode which variables influence each other. E.g., at the probabilistic level, the graph would encode which variables are conditionally independent of each other. In the satisfiability problems described so far, the graph was not mentioned, so the task was to decide whether there exists any model with any graph structure that satisfies the formula. In many studies, a researcher can infer information about the graph structure, combining observed and experimental data with existing knowledge. Indeed, learning graphical, causal structures from data has been the subject of a considerable amount of research (see, e.g., [21, 9, 13, 37] for recent reviews). Thus, we will study the satisfiability (resp. validity) of formulas with the additional requirement that the graph structure $𝒢$ is also given in the input. The goal would be to determine whether the formula is satisfied in a model (resp. is valid in all models) having the structure $𝒢$.

In fact, such a constraint validity problem is one of the central problems of causality. E.g., given a graph structure, Pearl’s prominent do-calculus [28] is often applied to show the validity of the equivalence between causal and probabilistic expressions. The impact of including the graph in the input on the complexity will be the second important question that we will study in this work (see Section 4). Thus, as a fifth dimension, we study the model structure:

$\bullet$ Model structure:

Specified by a graph as a part of the input or unconstrained.

We continue by giving an informal description of our results. A detailed description can be found in Section 3.

We first show that constraining the graph structure of the model makes the problem only harder in the sense that the unconstrained problem can be reduced to the constrained one, since the unconstrained problem can always be reduced to the constrained one with the complete directed acyclic graph as a model. It turns out that for the probabilistic or interventional layer together with basic or linear arithmetic, there is indeed a jump. The probabilistic layer becomes at least $\exists ℝ$-hard, while the interventional layer jumps from $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ to $\mathrm{𝖭𝖤𝖷𝖯}$. For all other combinations of the PCH layer and arithmetic, no such jump happens and the complexity stays the same, however, we require new proof techniques. The exact results are given compactly in Table 2 (for comparison, the complexity landscape for unconstrained models, can be found in Table 1).

Second, we consider the case when the underlying model is small; small here means that for the underlying probability distribution $P$, the number of tuples $(u_1,\mathrm{\dots },u_m)$ with $P(U_1=u_1,\mathrm{\dots },U_m=u_m)>0$ is polynomially bounded in the input size. For the interventional and counterfactual layer with polynomial arithmetic, this does not affect the complexity of the problem (again, new proof techniques are required), but for the probabilistic layer, the complexity drops down to $\exists {ℝ}^{\mathrm{\Sigma }}$, a new class contained in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. The full results are given compactly in Table 3.

To illustrate the main ideas behind Pearl’s Causal Hierarchy (PCH), we present below an example that, we hope, will make it easier to understand the formal definitions given in Section 2.2. In this example, we consider a hypothetical scenario involving three attributes represented by binary random variables: Age, modeled by $Z=1$ (young) and $Z=0$ (old), (COVID-19) Vaccination represented by $X=1$, if yes, and $X=0$ if not vaccinated, and Recovery, represented by $Y=1$ (and $Y=0$ meaning mortality). Below, we describe a structural causal model (SCM) that represents an unobserved true mechanism underlying this scenario and illustrates the canonical patterns of reasoning expressible at different levels of the PCH.

In this section, we describe the underlying formalism of the satisfiability problems that we consider. This will cover the first three parameter dimensions: the underlying arithmetic, with or without compact marginalization, and the PCH level. The other two dimensions then naturally follow since they are obtained by restricting the underlying model.

We always consider discrete distributions in the probabilistic and causal languages studied in this paper. We represent the values of the random variables as $\mathrm{𝑉𝑎𝑙}=\{0,1,\text{. . .},c-1\}$ and denote by $𝐗$ the set of random variables used in a system. Here, we use bold letters for sets of variables or sets of values. By capital letters $X_1,X_2,\text{. . .}$, we denote the individual variables and assume, w.l.o.g., that they all share the same domain $\mathrm{𝑉𝑎𝑙}$. A value of $X_i$ is often denoted by the corresponding lowercase letter $x_i$ or a natural number. In this section, we describe the 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=x$, where $X$ is a random variable and $x$ is a value in the domain of $X$. The language ${ℰ}_{\text{prop}}$ of propositional formulas over atomic events is defined as the closure of such events under the Boolean operators $\wedge$ and $\neg$. To specify the syntax of interventional and counterfactual events, we define the intervention and extend the syntax of ${ℰ}_{\text{prop}}$ to ${ℰ}_{\text{post-int}}$ and ${ℰ}_{\text{counterfact}}$, respectively, using the following grammars:

Note that since $\top$ means that no intervention has been applied, we can assume that ${ℰ}_{\text{prop}}\subseteq {ℰ}_{\text{post-int}}$.

The PCH consists of three languages ${ℒ}_1,{ℒ}_2,{ℒ}_3$, each of which is based on terms of the form $\mathbb{P}(\delta )$. For the (observational or associational) language ${ℒ}_1$, we have $\delta \in {ℰ}_{\text{prop}}$, for the (interventional) language ${ℒ}_2$, we have $\delta \in {ℰ}_{\text{post-int}}$ and for the (counterfactual) language ${ℒ}_3$, $\delta \in {ℰ}_{\text{counterfact}}$. 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 ${𝒯}_i^{\ast }$ of terms, with $i=1,2,3$, using the following grammars⁵⁵5In the given grammars, we omit the brackets for readability, but we assume that they can be used in a standard way.

where ${\delta }_1$ are formulas in ${ℰ}_{\text{prop}}$, ${\delta }_2\in {ℰ}_{\text{post-int}}$, ${\delta }_3\in {ℰ}_{\text{counterfact}}$.

The probabilities of the form $\mathbb{P}({\delta }_i)$ are called primitives or basic terms. In the summation operator ${\sum }_x$, we have a dummy variable $x$ which ranges over all values $0,1,\mathrm{\dots },c-1$. The summation ${\sum }_x𝐭$ is a purely syntactical concept which represents the sum $𝐭[0/x]+𝐭[1/x]+\text{. . .}+𝐭[c-1/x]$, whereby $𝐭[v/x]$, we mean the expression in which all occurrences of $x$ are replaced with value $v$. For example, for $\mathrm{𝑉𝑎𝑙}=\{0,1\}$, the expression ${\sum }_x\mathbb{P}(Y=1,X=x)$ semantically represents $\mathbb{P}(Y=1,X=0)+\mathbb{P}(Y=1,X=1)$.

We note that the dummy variable $x$ 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 ${𝒯}_i^{\text{base}}$ are just basic probabilities with the events given by the corresponding languages ${ℰ}_{\text{prop}}$, ${ℰ}_{\text{post-int}}$, or ${ℰ}_{\text{counterfact}}$. 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 ${𝒯}_i^{\text{poly}}$, 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 ${𝒯}_i^{\text{poly}}$ was originally introduced by Fagin, Halpern, and Megiddo [11] (for $i=1$) to be able to express conditional probabilities by clearing denominators. While this works for ${𝒯}_i^{\text{poly}}$, this does not work in the case of ${𝒯}_i^{\text{poly}⟨\mathrm{\Sigma }⟩}$, since clearing denominators with exponential sums creates expressions that are too large. But we could introduce basic terms of the form $\mathbb{P}({\delta }_i|\delta )$ with $\delta \in {ℰ}_{\text{prop}}$ explicitly. All our hardness proofs work without conditional probabilities but all our matching upper bounds are still true with explicit conditional probabilities.

Expressions like $\mathbb{P}(X=1)+\mathbb{P}(Y=2)\cdot \mathbb{P}(Y=3)$ are valid terms in ${𝒯}_{\text{1}}^{\text{poly}}$ and ${\sum }_z\mathbb{P}([X=0](Y=1,Z=z))$ and ${\sum }_z\mathbb{P}(([X=0]Y=1),Z=z)$ are valid terms in the language ${𝒯}_{\text{3}}^{\text{poly}⟨\mathrm{\Sigma }⟩}$, for example.

Now, let $\text{Lab}=\{\text{base},\text{base}⟨\mathrm{\Sigma }⟩,\text{lin},\text{lin}⟨\mathrm{\Sigma }⟩,\text{poly},\text{poly}⟨\mathrm{\Sigma }⟩\}$ denote the labels of all variants of languages. Then for each $\ast \in \text{Lab}$ and $i=1,2,3$, we define the languages ${ℒ}_i^{\ast }$ of Boolean combinations of inequalities in a standard way:

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. $\mathbb{P}(x)=\mathbb{P}(y)$ means $\mathbb{P}(x)\ge \mathbb{P}(y)\wedge \mathbb{P}(y)\ge \mathbb{P}(x)$.

The number $0$ can be encoded as an inconsistent probability, i.e., $\mathbb{P}(X=1\wedge X=2)$. In a language allowing addition and multiplication, any positive integer can be easily encoded from the fact $\mathbb{P}(\top )\equiv 1$, e.g. $4\equiv (1+1)(1+1)\equiv (\mathbb{P}(\top )+\mathbb{P}(\top ))(\mathbb{P}(\top )+\mathbb{P}(\top ))$. 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 [28, Sec. 3.2]. An SCM is a tuple $𝔐=(ℱ,P,$ $𝐔,𝐗)$, such that $𝐕=𝐔\cup 𝐗$ is a set of variables partitioned into exogenous (unobserved) variables $𝐔=\{U_1,U_2,\text{. . .}\}$ and endogenous variables $𝐗$. The tuple $ℱ=\{F_1,\text{. . .},F_n\}$ consists of functions such that function $F_i$ calculates the value of variable $X_i$ from the values $(𝐱,𝐮)$ of other variables in $𝐕$ as $F_i({\mathrm{𝐩𝐚}}_i,{𝐮}_i)$ ⁶⁶6We consider recursive models, that is, we assume the endogenous variables are ordered such that variable $X_i$ (i.e. function $F_i$) is not affected by any $X_j$ with $j>i$. Here, we also use the usual notation with capital letters and lowercase letters where ${\mathrm{𝐏𝐚}}_i$ are variables and ${\mathrm{𝐩𝐚}}_i$ is an assignment of values to those variables., where ${\mathrm{𝐏𝐚}}_i\subseteq 𝐗$ and ${𝐔}_i\subseteq 𝐔$. $P$ specifies a probability distribution of all exogenous variables $𝐔$. Since variables $𝐗$ depend deterministically on the exogenous variables via functions $F_i$, $ℱ$ and $P$ obviously define the joint probability distribution of $𝐗$.

Throughout this paper, we assume that domains of endogenous variables $𝐗$ are discrete and finite. In this setting, exogenous variables $𝐔$ could take values in any domain, including infinite and continuous ones. A recent paper [39] shows, however, that any SCM over discrete endogenous variables is equivalent for evaluating post-interventional probabilities to an SCM where all exogenous variables are discrete with finite domains.

As a consequence, throughout this paper, we assume that domains of exogenous variables $𝐔$ are discrete and finite, too.

For any basic ${ℰ}_{\text{int}}$-formula $X_i=x_i$ (which, in our notation, means $\text{do}(X_i=x_i)$), we denote by ${ℱ}_{X_i=x_i}$ the function obtained from $ℱ$ by replacing $F_i$ with the constant function $F_i(𝐯):=x_i$. We generalize this definition for all interventions specified by $\alpha \in {ℰ}_{\text{int}}$ in a natural way and denote as ${ℱ}_{\alpha }$ the resulting functions. For any $\phi \in {ℰ}_{\text{prop}}$, we write $ℱ,𝐮\vDash \phi$ if $\phi$ is satisfied for values of $𝐗$ calculated from the values $𝐮$. For $\alpha \in {ℰ}_{\text{int}}$, we write $ℱ,𝐮\vDash [\alpha ]\phi$ if ${ℱ}_{\alpha },𝐮\vDash \phi$. And for all $\psi ,{\psi }_1,{\psi }_2\in {ℰ}_{\text{counterfact}}$, we write $(i)$ $ℱ,𝐮\vDash \neg \psi$ if $ℱ,𝐮\vDash ̸\psi$ and $(ii)$ $ℱ,𝐮\vDash {\psi }_1\wedge {\psi }_2$ if $ℱ,𝐮\vDash {\psi }_1$ and $ℱ,𝐮\vDash {\psi }_2$.

Finally, for $\psi \in {ℰ}_{\text{counterfact}}$, let $S_{𝔐}(\psi )=\{𝐮\mid ℱ,𝐮\vDash \psi \}$.

We define ${⟦𝐞⟧}_{𝔐}$, for some expression $𝐞$, recursively in a natural way, starting with basic terms as follows ${⟦\mathbb{P}(\psi )⟧}_{𝔐}={\sum }_{𝐮\in S_{𝔐}(\psi )}P(𝐮)$ and, for $\delta \in {ℰ}_{\text{prop}}$, ${⟦\mathbb{P}(\psi |\delta )⟧}_{𝔐}={⟦\mathbb{P}(\psi \wedge \delta )⟧}_{𝔐}/{⟦\mathbb{P}(\delta )⟧}_{𝔐}$, assuming that the expression is undefined if ${⟦\mathbb{P}(\delta )⟧}_{𝔐}=0$. For two expressions ${𝐞}_1$ and ${𝐞}_2$, we define $𝔐\vDash {𝐞}_1\le {𝐞}_2$, if and only if, ${⟦{𝐞}_1⟧}_{𝔐}\le {⟦{𝐞}_2⟧}_{𝔐}.$ The semantics for negation and conjunction are defined in the usual way, giving the semantics for $𝔐\vDash \phi$ for any formula $\phi$ in ${ℒ}_3^{\ast }$.

The (decision) satisfiability problems for languages of the PCH, denoted by ${\text{Sat}}_{{ℒ}_i}^{\ast }$, with $i=1,2,3$ and $\ast \in \text{Lab}$, take as input a formula $\phi$ in ${ℒ}_i^{\ast }$ and ask whether there exists a model $𝔐$ such that $𝔐\vDash \phi$. Analogously, the validity problems for ${ℒ}_i^{\ast }$ consist in deciding whether, for a given $\phi$, $𝔐\vDash \phi$ holds for all models $𝔐$. From the definitions, it is obvious that variants of the problems for the level $i$ are at least as hard as their counterparts at the lower level.

In many studies, a researcher can infer information about the graph structure of the SCM, combining observed and experimental data with existing knowledge. Indeed, learning causal structures from data has been the subject of a considerable amount of research (see, e.g., [9, 13, 37] for recent reviews and [30, 23, 20, 33, 31] for current achievements). Thus, the problem of interest in this setting, which is a subject of this section, is to determine the satisfiability, resp., validity of formulas in SCMs with the additional requirement on the graph structure of the models.

Let $𝔐=(ℱ=\{F_1,\mathrm{\dots },F_n\},P,𝐔,𝐗=\{X_1,\mathrm{\dots },X_n\})$ be an SCM. We will assume that the models are semi-Markovian in the general case and Markovian in the graph constrained case⁷⁷7We note that the general semi-Markovian model, 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 new auxiliary “latent” variables $L_1,\mathrm{\dots },L_k$ which belong to the endogenous variables $𝐗$ of the model, but which are non-measurable in contrast to the “standard” observed / measurable variables. Then we can use such latent variables as nodes of a DAG but the joint probability distribution on $𝐗$ is restricted to only the measurable variables and ignores $L_1,\mathrm{\dots },L_k$. , Markovian means that the exogenous arguments $U_i,U_j$ of $F_i$, resp. $F_j$ are independent whenever $i\ne j$. We define that a DAG $𝒢=(𝐗,E)$ represents the graph structure of $𝔐$ if, for every $X_j$ appearing as an argument of $F_i$, $X_j\to X_i$ is an edge in $E$. DAG $𝒢$ is called a causal diagram of the model $𝔐$ [28, 3]. The satisfiability problems with an additional requirement on the causal diagram, take as input a formula $\phi$ and a DAG $𝒢$ with the task of deciding whether there exists an SCM with the structure $𝒢$ for $\phi$. In this way, for problems ${\text{Sat}}_{{ℒ}_i}^{\ast }$, we get the corresponding problems denoted as ${\text{Sat}}_{\text{DAG},{ℒ}_i}^{\ast }$, with $\ast \in \text{Lab}$.

An important feature of ${\text{Sat}}_{{ℒ}_i}^{\text{poly}}$ instances, over all levels $i=1,2,3$, is the small model property which says that, for every satisfiable formula, there is a model whose size is bounded polynomially with respect to the length of the input. This property was used to prove the memberships of ${\text{Sat}}_{{ℒ}_i}^{\text{poly}}$ in $\mathrm{𝖭𝖯}$ and in $\exists ℝ$ [11, 15, 22, 16]. Interestingly, membership proofs of ${\text{Sat}}_{{ℒ}_1}^{\text{lin}⟨\mathrm{\Sigma }⟩}$ in $\mathrm{𝖭𝖯}$^PP and ${\text{Sat}}_{{ℒ}_2}^{\text{lin}⟨\mathrm{\Sigma }⟩}$ in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ [8] rely on the property as well.

Apart from these advantages, the small model property is interesting in itself. For example, on the probabilistic layer, if a formula $\phi$ (without the summation) over variables $X_1,\mathrm{\dots },X_n$ is satisfiable, then there exists a Bayesian network $ℬ=(𝒢,P_{ℬ})$, with a DAG $𝒢$ over nodes $X_1,\mathrm{\dots },X_n$ and conditional probability tables $P_{ℬ}$ for each variable $X_i$, such that $\phi$ is true in $ℬ$ and the total size of the tables is bounded by a polynomial of $|\phi |$.

These have motivated the introduction of the small-model problem, denoted as ${\text{Sat}}_{\text{sm}\text{, }{ℒ}_1}^{\text{poly}⟨\mathrm{\Sigma }⟩}$, which is defined like ${\text{Sat}}_{{ℒ}_1}^{\text{poly}⟨\mathrm{\Sigma }⟩}$ with the additional constraint that a satisfying distribution should only have polynomially large support, that is, only polynomially many entries in the exponentially large table of probabilities are non-zero [4]. In the paper, the authors achieve this by extending an instance with an additional unary input $p\in \mathbb{N}$ and requiring that the satisfying distribution has a support of size at most $p$. We define ${\text{Sat}}_{\text{sm}\text{, }{ℒ}_2}^{\text{poly}⟨\mathrm{\Sigma }⟩}$ and ${\text{Sat}}_{\text{sm}\text{, }{ℒ}_3}^{\text{poly}⟨\mathrm{\Sigma }⟩}$ in a similar way. Formally, we use the following:

For two computational problems $A,B$, we will write $A{\le }_{\text{P}}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 a complexity class $𝒞$, if $A\in 𝒞$ and, for every other problem $B\in 𝒞$, it holds $B{\le }_{\text{P}}A$. By $\mathrm{𝚌𝚘}\text{-}𝒞$, we denote the class of all problems $A$ such that their complements $\overline{A}$ belong to $𝒞$.

To measure the computational complexity of ${\text{Sat}}_{{ℒ}_i}^{\ast }$, a central role play the following, well-known Boolean complexity classes $\mathrm{𝖭𝖯},\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤},\mathrm{𝖭𝖤𝖷𝖯},$ and $\mathrm{𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤}$ (for formal definitions see, e.g., [2]). Recent research has shown that the precise complexity of several natural satisfiability problems can be expressed in terms of the classes over the real numbers $\exists ℝ$ and $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$. Recall, that the existential theory of the reals $(\text{ETR})$ is the set of true sentences of the form

where $\phi$ is a quantifier-free Boolean formula over the basis $\{\vee ,\wedge ,\neg \}$ and a signature consisting of the constants $0$ and $1$, the functional symbols $+$ and $\cdot$, and the relational symbols , $\le$, and $=$. The sentence is interpreted over the real numbers in the standard way. The theory forms its own complexity class $\exists ℝ$ which is defined as the closure of the ETR under polynomial time many-one reductions [14, 5, 35]. A succinct variant of ETR, denoted as succ-ETR, and the corresponding class $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$, have been introduced in [38]. succ-ETR is the set of all Boolean circuits $C$ that encode a true sentence as in $(\text{<a href="\#S2.E1" title="Equation 1 ‣ 2.4 The (succinct) existential theory of the reals ‣ 2 Preliminaries ‣ Probabilistic and Causal Satisfiability: Constraining the Model" class="ltx\_ref ltx\_font\_italic"><span class="ltx\_text ltx\_ref\_tag">1</span></a>})$ as follows. Assume that $C$ computes a function ${\{0,1\}}^N\to {\{0,1\}}^M$. Then ${\{0,1\}}^N$ represents the node set of the tree underlying $\phi$ and $C(i)$ is an encoding of the description of node $i$, consisting of the label of $i$, its parent, and its two children. The variables in $\phi$ are $x_1,\mathrm{\dots },x_{2^N}$. As in the case of $\exists ℝ$, to $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$ belong all languages which are polynomial time many-one reducible to succ-ETR. $\exists ℝ$ and $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$ can also be defined in terms of real RAMs [10, 4]. These two classes correspond to nondeterministic polynomial and exponential time, respectively, on such machines.

In a breakthrough result, Renegar [32] showed that $\text{ETR}\in \mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. In addition, his result also shows that even if the formula contains an exponential number of arithmetic terms of exponential size with exponential degree, it is still possible to solve the formula in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$, as long as the number of variables is polynomially bounded.

For unconstrained models, we have a clear picture of the satisfiability landscape, see Table 1. Fagin et al. [11] prove the $\mathrm{𝖭𝖯}$-completeness for the probabilistic layer with basic and linear terms and the $\mathrm{𝖭𝖯}$-hardness with polynomial terms. Mossé et al. [22] prove that the latter is in fact complete for the existential theory of the reals $\exists ℝ$. They also prove that the same complexity results also hold for the interventional and counterfactual layers of the PCH. This means that the layer of the PCH does not have any impact on the complexity of the corresponding satisfiability problem. Things however change, when we add a marginalization operator. As shown in [8] if the arithmetic is basic or linear, then the satisfiability problem is complete for ${\mathrm{𝖭𝖯}}^{\mathrm{𝖯𝖯}}$, $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$, and $\mathrm{𝖭𝖤𝖷𝖯}$ when the PCH layer increases from probabilistic to counterfactual. If, however, the arithmetic is polynomial, then all three layers have the same complexity again, they are complete for the new class $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$ [38, 17, 8].

As our main result, we complete the complexity landscape of the probabilistic and causal satisfiability problems when we either constrain the graph structure of the SCM or when we force the model to be small.

As the first part of our main results, we classify the difficulty of the satisfiability problems when the graph structure is given as a part of the input. We will show that these cases are always at least as hard as the corresponding problems without specified graph structures. This is due to the fact that we can always take the complete acyclic graph. The most notable difference to the unconstrained problems happens at the interventional layer. Here we have an increase in complexity from $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ to $\mathrm{𝖭𝖤𝖷𝖯}$. We also compare our results to the model checking problem. Here we are not only given a graph structure but the full SCM and we need to check whether the model satisfies the input formula. It turns out that model checking is considerably easier. For instance, when the arithmetic is polynomial with marginalization, then even at the probabilistic layer, the satisfiability problem is $\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$-complete, while the corresponding model checking problem is in ${\mathrm{𝖭𝖯}}^{\mathrm{𝖯𝖯}}$ (Theorem 4).

Secondly, we consider the satisfiability problems with the small model property and investigate how the complexity increases across the PCH, in the presence of summation operators. In Definition 1, we defined the small model property for SCMs. In the original work of Fagin et al., there was no underlying SCM since they only dealt with the probabilistic layer, and a small model meant that we only have polynomially many entries in the table of the joint probability distribution of the (observed) variables. Since each observed variable is a function in the unobserved variables, both definitions are equivalent for semi-Markovian models as we show in Fact 3. Most notably, with polynomial arithmetic, at the probabilistic layer, having a small model reduces the complexity to $\exists {ℝ}^{\mathrm{\Sigma }}$, the existential theory of the reals enhanced with a compact summation operator. This was shown in [4] for a probabilistic model without an underlying SCM and with Fact 3 we show that it still holds for Definition 1. As soon as we are at the interventional or even counterfactual layer, then the complexity jumps, but only to $\mathrm{𝖭𝖤𝖷𝖯}$. Thus when we have a small model, the problem is hard for a Boolean class, although we have polynomial arithmetic and would have expected that the problem is hard for some theory over the reals. For linear arithmetic with a compact summation operator, it is known that the complexity increases along the PCH, and we show that the corresponding proofs of [8] are still valid if one requires a small-model property. The results are summarized in Figure 3.

A Bayesian network (BN) $ℬ=(𝒢,P_{ℬ})$ consists of a DAG $𝒢$ over nodes representing random variables $X_1,\mathrm{\dots },X_n$ and a distribution $P_{ℬ}$ which factorizes over $𝒢$, meaning that the joint probability $P_{ℬ}(x_1,\text{. . .},x_n)$ can be written as a product ${\prod }_{i=1}^n{P}_{ℬ}(x_i\mid {\mathrm{𝐩𝐚}}_i)$, where ${\mathrm{𝐩𝐚}}_i$ denotes the values $x_{j_1},\mathrm{\dots },x_{j_k}$ of parents ${\mathrm{𝐏𝐚}}_i$ of $X_i$ in $𝒢$. Then the distribution $P_{ℬ}$ is specified as a set of conditional probability tables for each variable $X_i$ conditioned on its parents in $𝒢$ [18]. So, for example, in the case of binary variables, even if the array representing the joint distribution has $2^n$ non-zero elements, it can still be compactly represented by a set of arrays of total size ${\sum }_{i=1}^n{2}^{|{\text{Pa}}_i|}$. This representation has many additional advantages, for example, enabling efficient probabilistic inference.

In the case of purely probabilistic languages, the problem ${\text{Sat}}_{\text{DAG},{ℒ}_1}^{\ast }$ can be read as follows: given a DAG $𝒢$ over nodes $𝐗$ of a Bayesian network (but not being given the distribution $P_{ℬ}$) and a formula $\phi$ in the language ${ℒ}_1^{\ast }$ decide whether there exists $P_{ℬ}$ such that $\phi$ is true in some BN $ℬ=(𝒢,P_{ℬ})$, where $P_{ℬ}$ factorizes over $𝒢$.

We start with the observation that ${\text{Sat}}_{{ℒ}_1}^{\ast }$ is not harder than ${\text{Sat}}_{\text{DAG},{ℒ}_1}^{\ast }$ for any $\ast \in \text{Lab}$.

One of the key components in the development of structural causal models is the do-calculus introduced by Pearl [27, 28], which allows one to estimate causal effects from observational data. The calculus can be expressed as a validity problem for intervention-level languages with the graph structure requirements on SCMs. In particular, the rules of the calculus can be seen as instances of validity problems for which equivalent graphical conditions in terms of $d$-separation are given. For example, the “insertion/deletion of observations” rule requires, for a given DAG $𝒢$, that, for all SCMs $𝔐$ with the causal structure $𝒢$, and for all values $𝐱,𝐲,𝐳,𝐰$, it holds $\mathbb{P}([𝐱]𝐲|[𝐱](𝐳,𝐰))=\mathbb{P}([𝐱]𝐲|[𝐱]𝐰)$. This rule can be written in a compact way as ${\sum }_{𝐱,𝐲,𝐳,𝐰}{(\mathbb{P}([𝐱]𝐲|[𝐱](𝐳,𝐰))-\mathbb{P}([𝐱]𝐲|[𝐱]𝐰))}^2=0$. In this section, we prove that, in general, the validity problem with polynomial arithmetic is very hard, namely we will see that it is complete for $\mathrm{𝚌𝚘}\text{-}\mathrm{𝗌𝗎𝖼𝖼}\text{-}\exists ℝ$.

To this goal, we study the complexity of the satisfiabilities with graph structure requirements in the case of the interventional languages. The base and linear languages are neither weak enough to be independent of the graph structure nor strong enough to be able to distinguish graph structures exactly. In particular the complexity of ${\text{Sat}}_{\text{DAG},{ℒ}_2}^{\text{base}⟨\mathrm{\Sigma }⟩}$ and ${\text{Sat}}_{\text{DAG},{ℒ}_2}^{\text{lin}⟨\mathrm{\Sigma }⟩}$ increases above the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-completeness of ${\text{Sat}}_{{ℒ}_2}^{\text{base}⟨\mathrm{\Sigma }⟩}$ and ${\text{Sat}}_{{ℒ}_2}^{\text{lin}⟨\mathrm{\Sigma }⟩}$. On the other hand, the polynomial languages are strong enough to encode the DAG structure of the model which implies that the complexity for these languages is the same as ${\text{Sat}}_{{ℒ}_2}^{\text{poly}⟨\mathrm{\Sigma }⟩}$.

An important tool for the proof of this theorem is the satisfiability of a Schönfinkel-Bernays sentence. The class of Schönfinkel–Bernays sentences (also called Effectively Propositional Logic, EPR) is a fragment of first-order logic formulas where satisfiability is decidable. Each sentence in the class is of the form $\exists 𝐱\forall 𝐲\psi$ whereby $\psi$ can contain logical operations $\wedge ,\vee ,\neg$, variables $𝐱$ and $𝐲$, equalities, and relations $R_i(𝐱,𝐲)$ which depend on a set of variables, but $\psi$ cannot contain any quantifier or functions. Determining whether a Schönfinkel-Bernays sentence is satisfiable is an $\mathrm{𝖭𝖤𝖷𝖯}$-complete problem [19] even if all variables are restricted to binary values [1].

If the graph $𝒢$ is complete, that is, all nodes are connected by an edge, it is equivalent to a causal ordering, an ordering $X_{i_1}\prec X_{i_2}\prec \mathrm{\dots }\prec X_{i_n}$, such that variable $X_{i_j}$ can only depend on variables $X_{i_k}$ with . If a causal ordering is given as a constraint, it does not change the complexity of the problem: