Complexity Classifications for Logic-Based Argumentation
2014 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, Vol. 15, no 3, 19- p.Article in journal (Refereed) Published
We consider logic-based argumentation in which an argument is a pair (Phi, alpha), where the support Phi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by Delta) that entails the claim alpha (a formula). We study the complexity of three central problems in argumentation: the existence of a support Phi subset of Delta, the verification of a support, and the relevance problem (given psi, is there a support Phi such that psi is an element of Phi?). When arguments are given in the frill language of propositional logic, these problems are computationally costly tasks: the verification problem is DP-complete; the others are Sigma(P)(2)-complete. We study these problems in Schaefers famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints built upon a fixed finite set of Boolean relations Gamma (the constraint language). We show that according to the properties of this language Gamma, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete, or Sigma(P)(2)-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or Sigma(P)(2)-complete. These last two classifications are obtained by means of algebraic tools.
Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2014. Vol. 15, no 3, 19- p.
Theory; Computational complexity; generalized satisfiability; logic-based argumentation; Schaefer
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-112491DOI: 10.1145/2629421ISI: 000343693300002OAI: oai:DiVA.org:liu-112491DiVA: diva2:766711
Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Austrian Science Foundation (FWF) [S11409-N23]2014-11-282014-11-282014-11-28