Trichotomy results on the complexity of reasoning with disjunctive logic programs

Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

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).

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings
Pages303-315
Number of pages13
DOIs
StatePublished - 2009
Event10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009 - Potsdam, Germany
Duration: Sep 14 2009Sep 18 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5753 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009
Country/TerritoryGermany
CityPotsdam
Period9/14/099/18/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Trichotomy results on the complexity of reasoning with disjunctive logic programs'. Together they form a unique fingerprint.

Cite this