Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs

We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities of rules. We show that each such class of programs has a finite representation, an...

Full description

Saved in:
Bibliographic Details
Published in:Theory and practice of logic programming 2011-11, Vol.11 (6), p.881-904
Main Author: TRUSZCZYSKI, MIROSAW
Format: Article
Language:English
Subjects:
Complexity
Dichotomies
Hardness
Logic programming
Mathematical analysis
Reasoning
Regular Papers
Representations
Semantics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities of rules. We show that each such class of programs has a finite representation, and for each of the classes definable in the schema, we characterize the complexity of the existence of an answer set problem. Next, we derive similar characterizations of the complexity of skeptical and credulous reasoning with disjunctive logic programs. Such results are of potential interest. On the one hand, they reveal some reasons responsible for the hardness of computing answer sets. On the other hand, they identify classes of problem instances, for which the problem is “easy” (in P) or “easier than in general” (in NP). We obtain similar results for the complexity of reasoning with disjunctive programs under the supported-model semantics.
ISSN:1471-0684
1475-3081
DOI:10.1017/S1471068410000463