标题： 命题归结中分面解释的复杂性 显示英文标题

标题： Complexity of Faceted Explanations in Propositional Abduction

摘要： 归纳推理是一种流行的非单调范式，旨在解释观察到的症状和表现。 它有许多应用，例如在人工智能和数据库更新中的诊断和规划。 在命题归纳中，我们专注于通过命题公式来指定知识。 命题归纳中的任务的计算复杂性已被系统地表征——甚至对布尔片段有详细的分类。 不出所料，最有洞察力的推理问题（计数和枚举）在计算上非常具有挑战性。 因此，我们考虑决策与计数之间的推理，使我们能够更好地理解解释，同时保持有利的复杂度。 我们引入了命题归纳的方面，这些方面是出现在某些解释（相关的）但不是所有解释（可舍去的）中的文字。 使用方面的推理提供了对解释中变化更细致的理解（异质的）。 此外，我们考虑两个解释之间的距离，从而更好地理解异质性/同质性。 我们在各种情况下全面分析了命题归纳的方面，包括在波斯特框架中的几乎完整的表征。 显示英文摘要

摘要： Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artificial intelligence and database updates. In propositional abduction, we focus on specifying knowledge by a propositional formula. The computational complexity of tasks in propositional abduction has been systematically characterized - even with detailed classifications for Boolean fragments. Unsurprisingly, the most insightful reasoning problems (counting and enumeration) are computationally highly challenging. Therefore, we consider reasoning between decisions and counting, allowing us to understand explanations better while maintaining favorable complexity. We introduce facets to propositional abductions, which are literals that occur in some explanation (relevant) but not all explanations (dispensable). Reasoning with facets provides a more fine-grained understanding of variability in explanations (heterogeneous). In addition, we consider the distance between two explanations, enabling a better understanding of heterogeneity/homogeneity. We comprehensively analyze facets of propositional abduction in various settings, including an almost complete characterization in Post's framework.