A Hierarchy of Tractable Subsets for Computing Stable Models
  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, Omega_1,Omega_2,..., with the following properties: first,
Omega_1 is the class of all stratified knowledge bases; second, if a knowledge
base Pi is in Omega_k, then Pi 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 Pi; third, for an arbitrary knowledge base Pi, we can find
the minimum k such that Pi belongs to Omega_k in time polynomial in the size of
Pi; and, last, where K is the class of all knowledge bases, it is the case that
union{i=1 to infty} Omega_i = K, that is, every knowledge base belongs to some
class in the hierarchy.
