Representative Sets in Propositional Abduction

技术摘要：命题归纳中的代表集 (Representative Sets in Propositional Abduction)

问题定义
本文研究了命题归纳中的“代表性归纳问题”（Representative Abduction Problem, REPABD），这是一个关于命题归纳解空间结构的判定问题。在标准的命题归纳中，给定一个知识库（$KB$）、一组假设（$H$）和一个显现（$M$），目标是寻找一个解释$E \subseteq H$，使得$KB \land E$是可满足的，且$KB \land E \models M$。

这项工作将重点从寻找单个解释转向分析解释集的覆盖范围。具体而言，给定一个由对称差（汉明距离）定义的距离度量 $d(E_1, E_2) = |E_1 \triangle E_2|$ 以及一个参数 $k \geq 0$，问题在于判断给定的解释集 $S$ 是否为 $k$-代表性的。如果每一个可能的解释 $E$（或者在变体 $\text{REPABD}_\subseteq$ 中是每一个子集极小解释）都与 $S$ 中的至少一个元素在汉明距离内不超过 $k$，则称集合 $S$ 是 $k$-代表性的。形式化地，$S$ 是 $k$-代表性的，若 $\bigcup_{E \in S} \{E' \in \mathcal{E}(I) \mid d(E, E') \leq k\} = \mathcal{E}(I)$。

研究方法
作者基于 Post 逻辑格（Post's lattice）中的布尔约束语言进行了细粒度复杂度分析。

1. 约束语言 ($\Gamma$)： 知识库被限制为原子项为集合 $\Gamma$ 中关系的合式联言公式。复杂度针对所有可能的 $\Gamma$ 选择进行了分类。
2. 代数工具： 本文利用原初正向定义（pp-definability）和无等式原初正向定义（efpp）来建立不同约束语言之间的可约性。关键代数概念包括共丛（co-clones）、关系丛（relational clones），以及对素关系（prime）、非冗余关系（irredundant）或常数关系（constant）的区分。
3. 复杂度框架：
   • 经典复杂度： 在多项式层级（PH）内对问题进行分析，特别关注其在 P、coNP、NP、$\Pi^P_2$ 和 $\Sigma^P_2$ 中的归属。
   • 参数化复杂度： 根据参数 $k$（距离）、$|H|$（假设）、$|M|$（显现）和 $|S|$（代表集大小）对问题进行分析。研究使用了 W-层级（例如 W[1]-硬度）和 FPT（固定参数可解）分类。
4. 归约： 作者建立了与编码理论问题（特别是覆盖半径问题 Covering Radius Problem 和最接近字符串问题 Closest String Problem）之间的联系，以推导硬度和可解性结果。

主要贡献与结果

1. 经典复杂度分类
本文对 $\text{REPABD}(\Gamma)$ 和 $\text{REPABD}_\subseteq(\Gamma)$ 提供了完整的分类：

• $\Pi^P_2$-完全性： 如果 $\Gamma$ 可以表达某些非平凡关系（特别是涉及 $II_2$ 中的 $IN_2$ 或 $II_0$），则该问题是 $\Pi^P_2$-完全的。
• coNP-硬度/完全性： 对于许多标准归纳（ABD）是可解的片段（如 Horn、dual-Horn、affine 或 2-CNF），REPABD 是 coNP-硬或 coNP-完全的。这显著地是由表达“平凡”一元关系 $t = \{(0), (1)\}$ 或特定非常数关系的能力所驱动的。
• 可解性 (P)：
  • 对于 $\text{REPABD}(\Gamma)$，该问题仅在约束语言非常受限（例如仅包含常数关系）的情况下属于 P。
  • 对于子集极小变体 $\text{REPABD}_\subseteq(\Gamma)$，本文识别出了更广泛的可解情况。如果 $\Gamma$ 由严格本质正向（EP$^-$）或严格本质负向（EN$^-$）子句组成（且无法表达等式），则该问题可以在多项式时间内求解。在这些情况下，通常存在唯一的子集极小解释，使得验证代表集变得平凡。

2. 参数化复杂度
作者在各种参数下分析了该问题：

• 参数 $k$ (距离)： 该问题通常是困难的。对于包含蕴含（$IM$）或特定负子句（$IS^2_1$）的语言，它是 coW[1]-硬的。对于本质正向语言，$\text{REPABD}(\Gamma, k)$ 的复杂度被证明与以半径 $r$ 为参数的覆盖半径问题（Covering Radius Problem）是 FPT 等价的。
• 参数 $|H|$ (假设)： 建立了一个二分法。如果 $\Gamma$ 是 Schaefer 语言（Horn、dual-Horn、affine 或 2-CNF），则通过穷举子集，该问题是 FPT 的（可在 $f(|H|) \cdot poly(n)$ 时间内求解）。否则，它是 para-coDP-硬或 para-NP-硬。
• 参数 $|M|$ (显现)： 对于任何可以表达平凡关系 $t$ 或常数关系 $T$ 的语言，该问题都是 para-coNP-硬的。
• 参数 $|S|$ (代表集大小)：
  • 对于包含特定正子句（$IS^2_{11}$）的语言，该问题是 para-coNP-硬的。
  • 对于严格本质正向语言（EP$^-$），该问题是 FPT 的。作者通过将问题归约为已知关于字符串数量是 FPT 的“最接近字符串问题”来证明这一点。

意义与主张
本文声称提供了第一个关于命题归纳中代表集的细粒度复杂度分类。其主要贡献包括：

1. 复杂度差距： 它表明虽然标准归纳是 $\Sigma^P_2$-完全的，但验证代表集的问题通常会降至 $\Pi^P_2$-完全或 coNP-完全，但除了知识库具有非常特殊的结构限制外，很少降至 P。
2. 子集中的可解性： 它揭示了子集极小变体（$\text{REPABD}_\subseteq$）对于本质正向/负向语言比一般变体具有显著更高的可解性，这一结果在一般情况下并不明显。
3. 与编码理论的联系： 本文建立了非单调推理与编码理论之间的新颖联系。它表明，REPABD 的完整参数化分类取决于解决覆盖半径问题的参数化复杂度。反之，它利用了最接近字符串问题的 FPT 性质来证明代表性归纳的 FPT 结果。
4. 开放问题： 作者指出，1-有效（1-valid）语言的确切复杂度仍然开放（怀疑是 DP-完全），并且覆盖半径问题的参数化复杂度是实现完整分类的关键瓶颈。

研究结论认为，询问关于解空间的“细粒度”问题（如覆盖范围和多样性）引入了与寻找单个解不同的计算挑战，通常需要利用代数逻辑和编码理论的工具来解决。