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
Primary area: causal reasoning
Keywords: complexity, causal reasoning, Pearl's Causal Hierarchy

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.

Decision: accept (poster)
Reviewer scores: 8, 3, 5, 8

Reviews and discussion:
<thread>
creation date:
1730658307994

thread_type:
official_review

<thread_object>
creator: reviewer_k9we

<content>
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.
Their 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).
The 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.
This 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.

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.

This 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).

One 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.

In 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.

While the authors generally motivate their approach, and introduce the necessary concepts, well, at some points there is improvement possible. 
- 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.
- 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.
Also, 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.

I end this section with a small list of small remarks and typos:
- 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.
- Page 2, line 065: add a space between "see, e.g.," and "(Pearl, 1988;".
- Page 6, line 314:  I would write that the sum "ranges" over all values, instead of "sums" over it.

questions:
Here are three questions that would increase the readibility in my opinion:
1. 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.
2. Page 6, line 289: What does it mean for a sum to be "equivalent" to another sum? Does the author(s) mean "equal"?
3. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730666653515

thread_type:
official_review

<thread_object>
creator: reviewer_j9db

<content>
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.

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.

questions:
None.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730730851175

thread_type:
official_review

<thread_object>
creator: reviewer_cuwx

<content>
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.

strengths:
(1)The paper studies an important theoretical problem for causal reasoning and answers some open problems in this field. 
(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.   
(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. 
(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.
(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.

questions:
(1)There are several operations in the structure: sum, marginalization, conditioning. What are their roles in the increasing complexities of the hierarchy?
(1)Could you give nontrivial examples to demonstrate different levels of reasoning and to illustrate the corresponding increasing complexities?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730850080118

thread_type:
official_review

<thread_object>
creator: reviewer_enri

<content>
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$.

strengths:
- I checked the proofs and most of them make sense to me. The proofs are also quite rigorous in my opinion.
- The paper is succinct and clearly structured. 
- 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.

Here are some suggestions:
1. 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.
2. 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.
3. 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.

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.
2. Why/when do queries with marginalization become important? How does this relate to existing works on marginalizing (forgetting) variables from causal models?
3. 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.

Minor typos:
- Line 816: "the second sums" -> "the second sum"
- Line 863: "$\frac{P(\delta)}{P(\delta')}$" -> "$\frac{P(\delta)}{P(\delta, \delta')}$", maybe?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732789040023

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised PDF

comment:
We would like to thank all the reviewers for their valuable time and thoughtful reviews. We also thank them for their constructive comments to improve the quality of our paper, which we have tried to take into account in the revised version. We have attempted to do the revision while staying within the permitted page limit. Below we provide more details on the modifications made.

## Reviewer enRi: 

> Stressing that the satisfiability problem does not assume anything about SCMs.

done: see the 2-nd Paragraph in Sec.2.2

> In Appendix A.2 proof of Lemma 14. I don’t know what "small model property" is.

done

> Minor typos

done


## Reviewer cUWX:

>  Some important results in the paper are related to some uncommon complexity classes like succ-ExistentialR-completeness

In Sec. 2.2 we give a new reference to a current survey paper Schaefer et al. (2024) on ∃R, including its succinct version — the complexity class succ∃R. Moreover, we give a new paragraph (the last one) in Subsection "Our Contribution" in the Introduction. There we stress the significance of this class and the importance of our completeness results for this class as well as for the other classes shown in equation (1) in the new version.

>  There is no a concrete example which demonstrates the increasing complexity results

We now show in the Introduction the relations between complexity classes for which completeness results have been proven (new equation (1)). Under the commonly accepted complexity assumptions, all inclusion relations are strict, which implies an increasing complexity of satisfiability problems (and their complements, the validity problems) across the PCH.

> Illustrate the graph structures of SCMs 

To help understand the basic concepts, including interventions, we provide additional material on SCM graph structures in Section B of the Appendix.


## Reviewer J9DB:

> In particular, you seem to fix VAL to some finite set. Is this to be understood that all your results (e.g. complexity of SAT) are relative to a fixed finite VAL?

We added a sentence mentioning that it is a fixed set.

> lines 195-200. The definition of SCMs here is very compact and should be expanded. E.g., you use the notation Pa_i for the parents of X_i (I suppose). A few words explaining the setting and notation used would be helpful.

We added some sentences explaining the parents, the relationship between endogenous and exogenous variables, and that this definition is not based on graphs

> line 206: Typo. "S_M" should be "S_M(\psi)".

done

> line 242: It would be good to mention here, or before, where "\exists R" and "succ-\exists R" are situated wrt. other complexity classes.

done: see Introduction new Eq. (1)


## Reviewer K9we:

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

done

> 2. Page 6, line 289: What does it mean for a sum to be "equivalent" to another sum? Does the author(s) mean "equal"?

done

> 3. Theorem 9: The proof

We added a sentence about the containment
</content>
</thread_object>

</thread>


Metareview:
metareview:
Pearl's Causal Hierarchy (PCH) outlines three levels of reasoning—probabilistic, interventional, and counterfactual—each representing increasing complexity in understanding causation. This paper explores the computational complexity of satisfiability problems within PCH, focusing on probabilistic and causal languages. Specifically, it examines whether a given set of formulas in these languages can be satisfied by some model. The main contribution is determining the exact computational complexities: languages that include addition and marginalization (via summation) result in NP^PP-, PSPACE-, and NEXP-complete satisfiability problems corresponding to the probabilistic, causal, and counterfactual levels of PCH, respectively. These findings show a clear increase in complexity across the PCH levels. Furthermore, for full languages that also allow multiplication, the complexity of satisfiability at the counterfactual level remains consistent with the lower levels, thereby resolving an open problem previously posed by Van der Zander et al. The paper also conducts a thorough analysis of the complexity of satisfiability across various logic fragments used to describe structural causal models, including probability comparisons and interventional counterfactuals. Overall, the study significantly enhances the understanding of the computational challenges inherent in different layers of causal reasoning.

All the reviewers comment that the paper provides a solid and rigorous theoretical contribution to causal reasoning. The reviewers provide a list of suggestions for improving the quality of the presentation. I recommend this paper for publication and invite the authors to consider the reviewers' suggestions for preparing the final draft of the manuscript.