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

Mirosław Truszczyński

doi:10.1017/S1471068410000463

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

Mirosław Truszczyński

Computer Science

Research output: Contribution to journal › Article › peer-review

25 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 language	English
Pages (from-to)	881-904
Number of pages	24
Journal	Theory and Practice of Logic Programming
Volume	11
Issue number	6
DOIs	https://doi.org/10.1017/S1471068410000463
State	Published - 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.

Funding

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

Funders	Funder number
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	IIS-0913459

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

Access to Document

10.1017/S1471068410000463

Cite this

@article{21288e8e4bfc478ebfa4107dbedd1d55,

title = "Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs",

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.",

keywords = "answer sets, complexity of reasoning, supported models",

author = "Miros{\l}aw Truszczy{\'n}ski",

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{\'n}ski 2009). The work was partially supported by the NSF Grant IIS-0913459. The author gratefully acknowledges several helpful comments from the anonymous referees.",

year = "2011",

month = nov,

doi = "10.1017/S1471068410000463",

language = "English",

volume = "11",

pages = "881--904",

number = "6",

}

TY - JOUR

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

AU - Truszczyński, Mirosław

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

PY - 2011/11

Y1 - 2011/11

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

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

KW - answer sets

KW - complexity of reasoning

KW - supported models

UR - http://www.scopus.com/inward/record.url?scp=80255135579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80255135579&partnerID=8YFLogxK

U2 - 10.1017/S1471068410000463

DO - 10.1017/S1471068410000463

M3 - Article

AN - SCOPUS:80255135579

SN - 1471-0684

VL - 11

SP - 881

EP - 904

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

IS - 6

ER -

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

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this