TY - GEN
T1 - Trichotomy results on the complexity of reasoning with disjunctive logic programs
AU - Truszczyński, Mirosław
PY - 2009
Y1 - 2009
N2 - 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).
AB - 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).
UR - https://www.scopus.com/pages/publications/70349880719
UR - https://www.scopus.com/pages/publications/70349880719#tab=citedBy
U2 - 10.1007/978-3-642-04238-6_26
DO - 10.1007/978-3-642-04238-6_26
M3 - Conference contribution
AN - SCOPUS:70349880719
SN - 3642042376
SN - 9783642042379
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 303
EP - 315
BT - Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings
T2 - 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009
Y2 - 14 September 2009 through 18 September 2009
ER -