A Hierarchy of Tractable Subsets for Computing Stable Models

Abstract

Finding the stable models of a knowledge base is a significant computational problem in artificial intelligence. This task is at the computational heart of truth maintenance systems, autoepistemic logic, and default logic. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Ω1, Ω2,..., with the following properties: first, Ω1 is the class of all stratified knowledge bases; second, if a knowledge base Π is in Ωk, then Π has at most k stable models, and all of them may be found in time O(lnk), where l is the length of the knowledge base and n the number of atoms in Π, third, for an arbitrary knowledge base Π, we can find the minimum k such that Π belongs to Ωk in time polynomial in the size of Π, and, last, where κ is the class of all knowledge bases, it is the case that ∪i=1∞ Ωi= κ, that is, every knowledge base belongs to some class in the hierarchy.