Generating All Abductive Explanations for Queries on Propositional Horn Theories
Generating All Abductive Explanations for Queries on Propositional Horn Theories
复制标题
生成命题喇叭理论查询的所有归纳解释
DOI：
10.1007/978-3-540-45220-1_18
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
K. Makino
中科院分区：
文献类型：
--
作者：
Thomas Eiter;K. Makino
溯因推理是一种基本的推理模式，在人工智能 (AI) 和相关学科中变得越来越重要。计算溯因解释是一个重要的问题，关于这个主题的文献越来越多。我们通过提出计算多重计算的新结果来为这一努力做出贡献。来自由 Horn CNF 表示的命题 Horn 理论的溯因查询的所有可能呈指数级增长的解释。这里的问题是是否可以有效地生成一些解释，以及在所有解释的情况下，计算是否可以在多项式总时间（或输出多项式时间）中进行，即在输入和输出的组合大小中的时间多项式中。我们探讨了 CNF 中查询的这些问题及其重要限制。在结果中，我们表明，从 Horn CNF 计算负查询文字的所有解释在多项式总时间内是不可行的，除非 P = NP，这解决了一个悬而未决的问题。然而，我们展示了如何在非循环霍恩理论多项式限制下分别计算输入多项式时间中的许多解释和多项式总时间中的所有解释。作为对先前结果的补充和扩展，这详细描述了计算霍恩理论查询的多重解释的计算复杂性。
Abduction is a fundamental mode of reasoning, which has taken on increasing importance in Artificial Intelligence (AI) and related disciplines. Computing abductive explanations is an important problem, and there is a growing literature on this subject. We contribute to this endeavor by presenting new results on computing multiple resp. all of the possibly exponentially many explanations of an abductive query from a propositional Horn theory represented by a Horn CNF. Here the issues are whether a few explanations can be generated efficiently and, in case of all explanations, whether the computation is possible inpolynomial total time(oroutput-polynomial time), i.e., in time polynomial in the combined size of the input and the output. We explore these issues for queries in CNF and important restrictions thereof. Among the results, we show that computing all explanations for a negative query literal from a Horn CNF is not feasible in polynomial total time unless P = NP, which settles an open issue. However, we show how to compute under restriction to acyclic Horn theories polynomially many explanations in input polynomial time and all explanations in polynomial total time, respectively. Complementing and extending previous results, this draws a detailed picture of the computational complexity of computing multiple explanations for queries on Horn theories.