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

Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

22 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). We obtain similar results for the complexity of reasoning with disjunctive programs under the supported-model semantics.

Original languageEnglish
Pages (from-to)881-904
Number of pages24
JournalTheory and Practice of Logic Programming
Volume11
Issue number6
DOIs
StatePublished - Nov 2011

Bibliographical note

Funding Information:
This paper is an extended version of the paper presented at the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (Truszczyński 2009). The work was partially supported by the NSF Grant IIS-0913459. The author gratefully acknowledges several helpful comments from the anonymous referees.

Keywords

  • answer sets
  • complexity of reasoning
  • supported models

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Artificial Intelligence

Fingerprint

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

Cite this