A Hierarchy of Tractable Subsets for Computing Stable Models
<|reference_start|>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.<|reference_end|>
@article{ben-eliyahu1996a,
    title={A Hierarchy of Tractable Subsets for Computing Stable Models},
    author={R. Ben-Eliyahu},
    journal={Journal of Artificial Intelligence Research, Vol 5, (1996), 27-52},
    year={1996},
    archivePrefix={arXiv},
    eprint={cs/9608104},
    primaryClass={cs.AI}
}