研究命题归结解空间的代表性集合，判断一组解释能否覆盖其他解释。
Representative Sets in Propositional Abduction
- 提出用对称差小于阈值k来判断解释集是否具有代表性。
- 在经典复杂度下完成完全分类，部分情况仍可高效求解。
- 揭示了非单调推理与编码理论中覆盖半径问题的潜在关联。
命题归结问题是典型的非单调推理形式，要求为给定现象寻找解释。近年来，研究者开始关注解空间的精细性质，而不仅限于单个解。例如，寻找解空间中足够相异的多个解（多样化解）。本文研究相关表示问题：给定解释集S，能否代表任意其他解释（即其对称差小于给定阈值k）。首先从经典复杂性角度进行分析，获得完整分类。尽管仅有少数情形是易解的，但复杂度提升通常低于预期。随后考察多个参数下的参数化复杂性，发现新的易解与难解情形。有趣的是，完整参数化分类需解决编码理论中的覆盖半径问题。据我们所知，此前尚未建立编码理论与非单调推理之间的有效联系，但当深入探究解空间时，此类联系似乎变得关键。
原文摘要 · Abstract (English)
The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。