Complexity results for disjunctive logic programming and application to nonmonotonic logics
Thomas Eiter, Georg Gottlob · 1993
Ben-Eliyahu and Dechter have shown that stable semantics of a large class of extended propositional disjunctive logic programs (EDLPs) can be efficiently expressed in the language of propositional logic. They left it as an open issue whether this possible for all such programs. We provide strong evidence that this is not so, which is a consequence of a precise complexity characterization of query answering problems for EDLPs. In particular, deciding the existence of an answer set and deciding occurrence of literals in any respectively every answer sets of a finite propositional EDLP are shown to be complete for classes within the polynomial hierarchy. The results have applications to nonmonotonic logics and provide new complexity results for autoepistemic logic and disjunctive default theories. 1 Introduction As pointed out by Gelfond and Lifschitz [5], traditional logic programming does not allow to deal directly with incomplete information, which is a shortcoming for convenient kno...