arXiv:2504.19944v1 交叉公告类型 摘要：我们研究了在概率性和因果推理中满足性问题的复杂性。对于有限域上的随机变量 $X_1, X_2, \ldots$，基本术语是原子事件 $X_i = x_i$ 上的命题公式的概率，例如 $P(X_1 = x_1)$ 或 $P(X_1 = x_1 \vee X_2 = x_2)$。这些基本术语可以使用加法（产生线性术语）或乘法（产生多项式术语）进行组合。概率性的满足性问题询问是否存在联合概率分布满足这些术语上的布尔组合不等式。Fagin 等人（1990）展示了对于基本和线性术语，该问题的复杂性为 NP 完全，使得其复杂性与布尔满足性问题相当，而 Mossé 等人（2022）证明了对于多项式术语，该问题属于实数存在理论的完全问题。 佩尔的因果层次（PCH）扩展了概率性设置，加入了干预和反事实推理，增强了语言的表达能力。然而，Mossé 等人（2022）发现满足性复杂性没有变化。Van der Zander 等人（2023）显示，在语言中引入归一化操作符会显著增加复杂性。 我们在这一研究领域的基础上，通过约束模型添加了两个新的维度。首先，我们固定底层结构因果模型的图形结构，受到佩尔的 do-因果计算等设置的启发，给出了不同算术和 PCH 级别上的几乎完整图景。第二，我们研究小型模型。虽然早期工作表明可满足实例可以拥有多项式大小的模型，但在紧凑归一化之后这不再得到保证。我们探讨了不同情境下，在小型模型约束下的满足性复杂性。