Abstract
Ibeling et al. (2023). axiomatize increasingly expressive languages of causation and probability, and Mosse et al. (2024) show that reasoning (specifically the satisfiability problem) in each causal language is as difficult, from a computational complexity perspective, as reasoning in its merely probabilistic or "correlational" counterpart. Introducing a summation operator to capture common devices that appear in applications -- such as the $do$-calculus of Pearl (2009) for causal inference, which makes ample use of marginalization -- van der Zander et al. (2023) partially extend these earlier complexity results to causal and probabilistic languages with marginalization. We complete this extension, fully characterizing the complexity of probabilistic and causal reasoning with summation, demonstrating that these again remain equally difficult. Surprisingly, allowing free variables for random variable values results in a system that is undecidable, so long as the ranges of these random variables are unrestricted. We finally axiomatize these languages featuring marginalization (or more generally summation), resolving open questions posed by Ibeling et al. (2023).
Abstract (translated)
Ibeling 等人（2023）证明，对于越来越表达性的因果和概率语言，归约是一个越来越困难的问题。Mosse 等人（2024）表明，每个因果语言中的推理（特别是不满足问题）从计算复杂性的角度来看，与它的仅概率或“相关性”同义。引入求和操作来捕捉应用中常见的设备——例如 Pearl 的因果推理中的 $do$- 计算法（该方法充分利用边际化），Van der Zander 等人（2023）部分地将这些之前的复杂性结果扩展到具有边际化的因果和概率语言中。我们完成了这个扩展，完全刻画了使用求和操作的概率和因果推理的复杂性，表明这些 again 仍然同等困难。令人惊讶的是，只要随机变量的取值范围不受限制，允许自由变量会导致一个不可判定系统。最后，我们解决了这些具有边际化特点的语言（或更一般地求和操作），从而解决了 Ibeling 等人（2023）提出的问题。
URL
https://arxiv.org/abs/2405.03069
