Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs

DOI10.1007/978-3-642-04238-6_26MaRDI QIDQ3643127zbMATH OpenOpenAlexFDO

Authors Mirosław Truszczyński

Publication date 10 November 2009

Published in Logic Programming and Nonmonotonic Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2816

Mathematics Subject Classification ID

Logic programming (68N17) Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

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. To appear in Theory and Practice of Logic Programming (TPLP)

Recommendations

• Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
• On the computational cost of disjunctive logic programming: Propositional case
• Backdoors to normality for disjunctive logic programs
• Complexity of computing with extended propositional logic programs
• scientific article; zbMATH DE number 4166939

Cited in

(5)

• On the computational cost of disjunctive logic programming: Propositional case
• Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
• The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
• scientific article; zbMATH DE number 6963530 (Why is no real title available?)
• Logic for Programming, Artificial Intelligence, and Reasoning

This page was built for publication: Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3643127)