The Complexity of Circumscriptive Inference in Post’s Lattice
The Complexity of Circumscriptive Inference in Post’s Lattice
复制标题
波斯特格中限制推理的复杂性
DOI：
10.1007/s00224-010-9311-6
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
Michael Thomas
中科院分区：
文献类型：
--
作者：
Michael Thomas
限制是使用不完整信息进行推理的最重要的形式主义之一。它相当于在扩展的封闭世界假设下进行推理，可以得出这样的结论：从给定的知识库推导出来的事实都是满足给定属性的事实。在本文中，我们研究了命题限制中推理的几种形式化的计算复杂性，其中知识库是通过仅使用一组受限布尔函数的命题理论来描述的。为了系统地涵盖所有可能的布尔函数集，我们使用波斯特格。在它的帮助下，我们可以确定除两类可能的布尔函数之外的所有类别的限制推理的复杂性。这些问题中的每一个都被证明是 $\protect \ensuremath {\mathrm {\Pi ^{\mathrm{p}}_{2}}}$-完全、coNP-完全或可在对数空间中解决。特别是，我们表明在一般情况下，除非 P=NP，否则只有文字理论承认多项式时间算法，而对于某些受限变体，可处理边界与经典命题推理相同。
Circumscription is one of the most important formalisms for reasoning with incomplete information. It is equivalent to reasoning under the extended closed world assumption, which allows to conclude that the facts derivable from a given knowledge base are all facts that satisfy a given property. In this paper, we study the computational complexity of several formalizations of inference in propositional circumscription for the case that the knowledge base is described by a propositional theory using only a restricted set of Boolean functions. To systematically cover all possible sets of Boolean functions, we use Post’s lattice. With its help, we determine the complexity of circumscriptive inference for all but two possible classes of Boolean functions. Each of these problems is shown to be either $\protect \ensuremath {\mathrm {\Pi ^{\mathrm{p}}_{2}}}$-complete, coNP-complete, or solvable in logspace.In particular, we show that in the general case, unless P=NP, only literal theories admit polynomial-time algorithms, while for some restricted variants the tractability border is the same as for classical propositional inference.