找到因果推理中可满足性问题的首个可解路径，突破经典计算瓶颈。
Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
- 基于参数化复杂度，用变量数和基图树宽等参数设计高效算法
- 首次实现关键概率与反事实片段的固定参数可满足性求解
- 适合研究因果推理、形式化验证及算法设计的学者参考
Pearl因果层级（PCH）是推理概率、干预和反事实陈述的核心框架，但其公式可满足性问题在几乎所有经典设置下都存在计算不可行性。本文从参数化复杂度视角重新审视该挑战，首次识别出通往可解性的路径。我们为关键的概率与反事实片段提供了固定参数算法和XP算法，以基图树宽和变量数量等为参数，并给出匹配的难解性结果，精确刻画了可解性的边界。技术上，我们摒弃传统的动态规划范式，转而利用良定义因果模型的结构特征，构建了一套全新的因果推理算法工具集。
原文摘要 · Abstract (English)
Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。