We study formal languages which are capable of fully expressing quantitative
probabilistic reasoning and do-calculus reasoning for causal effects, from a
computational complexity perspective. We focus on satisfiability problems whose
instance formulas allow expressing many tasks in probabilistic and causal
inference. The main contribution of this work is establishing the exact
computational complexity of these satisfiability problems. We introduce a new
natural complexity class, named succ$\exists$R, which can be viewed as a
succinct variant of the well-studied class $\exists$R, and show that the
problems we consider are complete for succ$\exists$R. Our results imply even
stronger algorithmic limitations than were proven by Fagin, Halpern, and
Megiddo (1990) and Moss\'{e}, Ibeling, and Icard (2022) for some variants of
the standard languages used commonly in probabilistic and causal inference.

研究员从计算复杂性的角度出发，研究了能够完全表达数量化概率推理和因果效应的形式语言。研究集中于可表达许多概率和因果推断任务的可满足性问题，并建立了这些可满足性问题的确切计算复杂性。研究结果表明，一些在概率和因果推断中常用的标准语言的变体的算法限制更强。

关于概率和因果推理的困难程度

The Hardness of Reasoning about Probabilities and Causality

We propose a formalization of the three-tier causal hierarchy of association,
intervention, and counterfactuals as a series of probabilistic logical
languages. Our languages are of strictly increasing expressivity, the first
capable of expressing quantitative probabilistic reasoning -- including
conditional independence and Bayesian inference -- the second encoding
do-calculus reasoning for causal effects, and the third capturing a fully
expressive do-calculus for arbitrary counterfactual queries. We give a
corresponding series of finitary axiomatizations complete over both structural
causal models and probabilistic programs, and show that satisfiability and
validity for each language are decidable in polynomial space.

本研究将 3 层因果关系层次结构分为概率逻辑语言模型，第一层表达定量概率推断，第二层编码用于因果效应的 do-calculus 推理，第三层捕捉任意反事实查询。相关的公理化表达完全考虑了因果模型和概率编程，并证明了每种语言的可满足性和有效性都可以在多项式空间内可判定。