因果推理和概率推理难度一样？

Is Causal Reasoning Harder than Probabilistic Reasoning?

Milan Mossé, Duligur Ibeling, Thomas Icard

Abstract

Many tasks in statistical and causal inference can be construed as problems of entailment in a suitable formal language.

We ask whether those problems are more difficult, from a computational perspective, for causal probabilistic languages than for pure probabilistic (or “associational”) languages. Despite several senses in which causal reasoning is indeed more complex—both expressively and inferentially—we show that causal entailment (or satisfiability) problems can be systematically and robustly reduced to purely probabilistic problems. Thus there is no jump in computational complexity. Along the way we answer several open problems concerning the complexity of well known probability logics, in particular demonstrating the ∃Rcompleteness of a polynomial probability calculus, as well as a seemingly much simpler system, the logic of comparative conditional probability.

更多内容可参考原论文。

其他参考：

最新Tractability易处理的因果推理

80PPT 概率编程with Fast Exact Symbolic Inference 快速准确符号推理

小数据大任务 实现框架开源

再发：迄今为止 脑网络结构功能模块元素 最全面复杂清晰 类芯片多图及分解