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

Producción científica: Article › revisión exhaustiva

25 Citas (Scopus)

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	881-904
Número de páginas	24
Publicación	Theory and Practice of Logic Programming
Volumen	11
N.º	6
DOI	https://doi.org/10.1017/S1471068410000463
Estado	Published - nov 2011

Nota bibliográfica

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.

Financiación

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.

Financiadores	Número del financiador
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

ASJC Scopus subject areas

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

Acceder al documento

10.1017/S1471068410000463

Otros archivos y enlaces

Citar esto

@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 - https://www.scopus.com/pages/publications/80255135579

UR - https://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

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto