首次系统分析命题归因问题的细粒度复杂度，突破Σ²ᴾ难题的暴力搜索下限。
A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
- 以变量数n为参数，分析非单调推理的复杂度
- 首个实现Σ²ᴾ难题优于暴力搜索的算法，打破理论下限
- 在强指数时间假设下证明多数情形无法优化，适合复杂度研究者
布尔可满足性问题（SAT）是单调推理的经典范例，因其快速求解器和严谨的细粒度复杂度结果而备受关注。然而对于非单调推理（如归因推理），除经典复杂度理论外知之甚少。本文首次尝试弥合单调与非单调推理间的差距，通过分析知识库中变量数n这一看似被忽视但自然的参数，研究难解归因问题的复杂度。针对Σ²ᴾ、NP及coNP完全片段，获得若干正向结果，首次实现Σ²ᴾ完全问题优于穷举搜索的算法（据我们所知）。同时给出下界结果，在强指数时间假设下排除多数情形的改进可能。
原文摘要 · Abstract (English)
The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained complexity results. However, for non-monotonic reasoning, e.g., abductive reasoning, comparably little is known outside classic complexity theory. In this paper we take a first step of bridging the gap between monotonic and non-monotonic reasoning by analyzing the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n: the number of variables in the knowledge base. We obtain several positive results for $Σ^P_2$- as well as NP- and coNP-complete fragments, which implies the first example of beating exhaustive search for a $Σ^P_2$-complete problem (to the best of our knowledge). We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。