From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy

Thanks for your positive assessment of our work and the suggestions to improve the presentation. We will incorporate them.

Regarding the importance of marginalization, it is the standard notation in probability theory, any textbook on probability theory would include marginalization operators. It is more surprising that logicians have removed the marginalization operators from their considerations. Without marginalization, the expressiveness is the same for finite domains by expanding the sum, e.g. ∑_{x=1}^5 P(X=x) becomes P(X=1)+P(X=2)+P(X=3)+P(X=4)+P(X=5). However, when studying algorithmic and complexity aspects of probabilistic, causal, and counterfactual reasoning, enabling the marginalization for representing queries in a common, compact ways plays a crucial role, because the computational complexity is a function of the length of the input query. We can try to emphasizes this more in the introduction.

Questions:

• Page 4: That is true. We will clarify this.
• Page 6: Yes, we mean equal. We will clarify this, too.
• Theorem 9: Thanks for pointing this out. We will add a sentence about the containment to the proof idea.

We thank the reviewer for their review, but regret that they offer such a low score whilst hardly engaging with our paper at all.

We do not agree with the reviewer, that our paper is a pure logic paper or that it is a pure complexity theory paper for logics for causal reasoning.

Our main contribution is to establish the possibilities and limitations of algorithmic reasoning across the three levels of Pearl's hierarchy, including probabilistic, causal, and counterfactual reasoning. The algorithmic aspects of these reasoning tasks are critical in the fields of ML and AI and have been the focus of extensive research within the community. This includes both the development of specific algorithms and heuristics for inference and the study of the computational efficiency limitations of these methods. The rich body of literature on these topics is exemplified by the references provided in our paper, including the seminal work by Cooper (1990) and by Fagin et al. (1990) as well as by Ibeling and Icard (2020), Littman et al. (1998), Nilsson (1986), Park and Darwiche (2004), Roth (1996), Shpitser and Pearl (2008), van der Zander et al. (2023), published, e.g., in Artificial Intelligence, Journal of Artificial Intelligence Research, IJCAI, or AAAI.

The importance of establishing exact completeness results for probabilistic, causal, and counterfactual reasoning, as stated in our paper, lies in their implications for algorithmic approaches to solving these problems. Assuming the widely accepted belief that ∃R ≠ NP or NP ≠ PSPACE, the completeness of a problem highlights inherent limitations in applying algorithmic techniques, such as dynamic programming, divide-and-conquer, tree-width algorithms, SAT or ILP solvers, which are effective for NP-complete problems. This, in turn, justifies the use of heuristics, despite their potential for exponential worst-case complexity.

While the algorithmic and complexity aspects of probabilistic reasoning are well-studied and well-understood (e.g., Fagin et al. (1990), Cooper (1990), Ibeling and Icard (2020)), we have extended these results to queries expressed in a commonly used format. Furthermore, we have provided the first complexity results for answering causal and counterfactual queries formulated in a widely accepted manner. In our opinion, these results constitute an important contribution to the field of “causal reasoning” listed as one of the ICLR topics.

On the other hand, our work is NOT purely a logic paper. As emphasized in the paper, all languages that use the summation operator are semantically equivalent to those without it. What is novel about using the summation operator, however, is its ability to provide a compact and common representation of queries. This representation is crucial for studying the algorithmic and complexity aspects of probabilistic, causal, and counterfactual reasoning.

Thanks for your review. Below we respond to your comments and answer your questions.

Comments

(1) We think that checking validity is an important task in ML and AI and understanding how hard it is to check that a given property is valid, e.g., in a Structural Causal Model (SCM) of interest, is an important issue. We would like to emphasize that although the computational complexity results of our work mainly concern satisfiability problems, they also establish validity complexity because satisfiability and validity testing are complementary.

(2) ∃R, and also succ-∃R, are complexity classes that have become very important in the recent years. See the current survey [Schaefer, Cardinal, Miltzow The existential theory of the reals as a complexity class: A compendium. arXiv (2024)]. As we mentioned in our response to the reviewer J9DB, the importance of establishing exact completeness results for probabilistic, causal, and counterfactual reasoning, as stated in our paper, lies in their implications for algorithmic approaches to solving these problems. Assuming widely accepted complexity assumptions, the completeness of a problem highlights inherent limitations in applying algorithmic techniques and justifies the use of approximations and heuristics.

In particular, using succ-∃R-completeness as a yardstick for measuring 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 a surprising result, as the difference between the expressive power of both settings is huge.

(3) For concrete examples of queries, which demonstrate the increasing complexity results, see our answers to your questions below.

(4) In fact, Pearl's causal hierarchy can be thought of as providing ever more opportunities to manipulate the SCM: from pure observation, through intervention (manipulation) of the SCM, to the simultaneous generation of several manipulated SCMs. We agree that to explain a single intervention, it would indeed be appropriate to use the graph structure of the SCM. However, due to space constraints we could not do this. Instead, to help understand these concepts, we provide in Section B in appendix, an example for reasoning on all levels of the hierarchy. In the final version, we will try to present the concepts already in Section 2.1 in a more clear way and additionally, in Section B we will use the graph structure of the SCM to explain an intervention.

Questions

(1) "Operations in the structure and their roles in the increasing complexities of the hierarchy": The relation is summarized in Table 1. There are three dimensions of increasing difficulty:

First, the three levels of Pearls hierarchy (from left to right) which allow to formulate basic terms P(δ) used in queries. The complexity increases from: observational (probabilistic) events δ, like X = 1 ∧ Y = 1 (meaning, e.g., drug treatment and recovery), through interventional, like [X = 1] Y = 1 (meaning, e.g., recovery after intervention "drug treatment"), to the counterfactual events δ, like [X=1](Y =1) | (X=0, Y =0)) (meaning, e.g., a conditional event: recovery after drug treatment conditioned by an event, not treatment and the patient died). (Note, that we use the notation $P([X=x] Y=y)$ for the post-interventional distribution, which is often denoted as P(Y=y | do(X=x)), as the notation is more convenient for counterfactual reasoning)

Second, the power of arithmetic operations used to formulate queries involving the basic terms P(δ): none = "basic" (one can only formulate queries using relations like P(δ) ≤ P(δ') and combine them using Boolean operators ∧ and ¬), linear operations demoted as "lin" (one can formulate queries like P(δ) + P(δ') ≤ P(δ'')), addition and multiplication = "poly" (one can formulate queries like P(δ)*P(δ') + P(δ'') ≤ 1/2). Here the computational complexity increases from basic, through lin, to poly.

The third dimension is whether we do not allow marginalization (upper three lines of the table) or we have marginalization (lower three lines), as e.g. in $\sum_{x,y} (P(X=x, Y=y) - P(X=x) P(Y=y))^2=0$ to express independence of X and Y.

The case without marginalization was settled in previous work and our main contribution is to settle the computational complexity with marginalization. (Exponential) sums are the concrete realization of marginalization. In this sense, sums and marginalization are the same. Conditioning has only minor effects on the hardness of the problem.

(2) The examples from left to right are given by the power of Pearl's hierarchy. The difference from basic/lin to poly is due to the fact that one can use multiplications to formulate statements about reals numbers. An example at the interventional level involving marginalization is the adjustment formula. If you want to see the increasing complexities, one needs to look at the formulas in our hardness proofs.

• Thanks for your thoughtful suggestions on the structure of the paper. We will try to incorporate them.
• In particular we will emphasize more clearly that the satisfiability problem (and its complement, the validity problem) does not assume anything about SCMs, nor does the causal structure. However, we will additionally mention that our languages allow queries of the form φ ⇒ Ψ which enable us to verify satisfiability, resp., the validity, for the formula Ψ in Structural Causal Models (SCMs) which satisfy properties expressed by the formula φ, whereby φ can encode a graph structure. Thus, the formalism used in our work allows for the formulation of a wide range of queries.
• In addition, we will provide examples of queries expressed in the analyzed languages across the PCH.

Questions

• Indeed, validity testing is one of the main and natural applications. Since satisfiability and validity testing are complements of each other, it does not matter which of the problems one studies. From a technical point of view, satisfiability testing problems are often easier to study. Below we discuss some examples of validation testing applications where queries are typically expressed in languages that use the marginalization / summation operator.
• A famous example for a formula with marginalization is the adjustment-set formula P([x] y) = \sum_{z} P{y | x, z) P(z) (AS), see e.g. [Pearl, Glymour, Jewell: Causal Inference in Statistics - A Primer, Eq. (3.5)]. Again, we would like to remind that in our work we use the notation P([x] y)$for the post-interventional distribution, which is commonly denoted as$P(y | do(x))$. However, for the analysis of counterfactual reasoning, the notation$P([x] y)$ is much more convenient.
• A validity query regarding the adjustment formula can be expressed as φ ⇒ (AS), where φ is a formula describing certain properties that a SCM of interest should satisfy. In particular, φ can specify the causal structure (graph) of the SCM. This example nicely illustrates the application of validity testing to identify causal effects.
• Another example would be the prominent front-door adjustment [Pearl, Biometrika, 82(4):669–688, 1995] formula P([x] y) = \sum_{z} P(z | x} \sum_{x'} P{y | x', z) P(x') (FD). Again, we can formulate a query as φ ⇒ (FD) and test the validity of this implication. Similarly, validity testing can be applied in other cases.
• Marginalization for forgetting variables is a special case when the sum of a single probabilistic primitive is taken, where the primitive only contains a conjunction of variables. We consider this case in Proposition 1. If the sum is taken of a more complex term like in the adjustment formula or a primitive containing disjunctions, the result is more complex than just forgetting variables.
• Small model property means that whenever there is a satisfying probability distribution, then there is also one with only polynomially many non-zero elementary probabilities. (Note that the probability distribution on n random variables has 2^n entries.) Some of the referenced literature has based their results on such a small model property.