arXiv:2405.07373v3 通知类型: 替换 摘要：皮尔（Pearl）因果层次（PCH）框架形式化了三种类型的推理：概率的（即纯粹观察性的）、干预性的和反事实的，这些反映了人类关于因果关系的日益复杂的思维过程。我们研究了在这个框架下的计算复杂性方面的问题，主要集中在概率性和因果性语言在PCH中的满足问题。也就是说，给定一套标准的概率性和因果性语言公式，是否存在一个模型能够满足这些公式？ 我们的主要贡献是证明了精确的计算复杂性，表明允许加法和边际化（通过求和操作符）的语言导致NP^PP、PSPACE-和NEXP完备的满足性问题，这取决于PCH的层次。这些是首次展示PCH中严格递增复杂性的结果：从概率性推理到因果性和反事实推理。另一方面，在全语言的情况下，即允许加法、边际化和乘法，我们证明了反事实层的满足性与概率性和因果性层保持一致，解决了领域内的一个开放问题。