ON THE COMPUTATIONAL COST OF DISJUNCTIVE LOGIC PROGRAMMING - PROPOSITIONAL CASE

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of d eciding whether a disjunctive logic program is consistent is investiga ted for a variety of well-known semantics, as well as the complexity o f deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i .e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the co nsistency check is Sigma(2)(P)-complete for the disjunctive stable mod el semantics (in the total as well as partial version), the iterated c losed world assumption, and the perfect model semantics, and we show t hat the inference problem for these semantics is Pi(2)(P)-complete; an alogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and oth er more sophisticated variants of the closed world assumption. Further more, we use the close ties between the logic programming framework an d other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal the ories.