arXiv:2505.10201v1 交叉类型：公告 摘要：布尔可满足性问题（SAT）是一个典型的单调推理示例，由于快速求解器的存在，它在实践中引起了极大的关注，并得到了严格的细粒度复杂性结果的补充。然而，在单调推理之外，例如 abduction 推理，除了经典的复杂性理论之外，我们知道的相对较少。在本文中，我们通过分析不可计算 abduction 问题在知识库变量数量 n 下的复杂性，率先尝试弥合单调推理与非单调推理之间的差距。我们获得了几个对于 $\Sigma^P_2$-、NP-以及 coNP-完全片段的积极结果，这在某种程度上意味着（据我们所知）第一个避开穷举搜索的 $\Sigma^P_2$-完全问题的例子。我们还提供了下界，并且对于许多片段，排除了在强指数时间假设下的改进可能性。