research-article

Complexity Classifications for Logic-Based Argumentation

Authors:

Nadia Creignou,

Johannes SchmidtAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 15, Issue 3

Article No.: 19, Pages 1 - 20

https://doi.org/10.1145/2629421

Published: 04 August 2014 Publication History

Abstract

We consider logic-based argumentation in which an argument is a pair (Φ, α), where the support Φ is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by Δ) that entails the claim α (a formula). We study the complexity of three central problems in argumentation: the existence of a support Φ⊆Δ, the verification of a support, and the relevance problem (given ψ, is there a support Φ such that ψ ∈ Φ?). When arguments are given in the full language of propositional logic, these problems are computationally costly tasks: the verification problem is DP-complete; the others are Σ^p₂-complete. We study these problems in Schaefer's 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 Γ (the constraint language). We show that according to the properties of this language Γ, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete, or Σ^p₂-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 Σ^p₂-complete. These last two classifications are obtained by means of algebraic tools.

References

[1]

E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. 2005. The complexity of satisfiability problems: Refining Schaefer's theorem. In MFCS. 71--82.

Digital Library

[2]

P. Besnard and A. Hunter. 2001. A logic-based theory of deductive arguments. Artif. Intell. 128 (2001), 203--235.

Digital Library

[3]

P. Besnard and A. Hunter. 2008. Elements of Argumentation. MIT Press.

Digital Library

[4]

V. G. Bodnarchuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. I, II. Cybernetics 5 (1969), 243--252, 531--539.

[5]

E. Böhler, S. Reith, H. Schnoor, and H. Vollmer. 2005. Bases for Boolean co-clones. Inf. Process. Lett. 96, 2 (2005), 59--66.

Digital Library

[6]

C. Chesñevar, A. Maguitman, and R. Loui. 2000. Logical models of argument. ACM Comput. Surv. 32 (2000), 337--383.

Digital Library

[7]

S. A. Cook. 1971. The complexity of theorem proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM Press, 151--158.

Digital Library

[8]

N. Creignou, U. Egly, and J. Schmidt. 2012. Complexity of logic-based argumentation in Schaefer's framework. In Computational Models of Argument-COMMA 2012 (Frontiers in Artificial Intelligence and Applications), Vol. 245. IOS Press, 237--248.

[9]

N. Creignou, S. Khanna, and M. Sudan. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM.

Digital Library

[10]

N. Creignou, Ph. G. Kolaitis, and B. Zanuttini. 2008. Structure identification of Boolean relations and plain bases for co-clones. J. Comput. Syst. Sci. 74, 7 (2008), 1103--1115.

Digital Library

[11]

N. Creignou, J. Schmidt, and M. Thomas. 2012. Complexity classifications for propositional abduction in Post's framework. J. Logic Comput. 22, 5, 1145--1170.

Digital Library

[12]

N. Creignou, J. Schmidt, M. Thomas, and S. Woltran. 2011. Complexity of logic-based argumentation in Post's framework. Argument & Computation 2, 2--3 (2011), 107--129.

[13]

N. Creignou and H. Vollmer. 2008. Boolean constraint satisfaction problems: when does Post's lattice help&quest; In Complexity of Constraints, N. Creignou, Ph. G. Kolaitis, and H. Vollmer (Eds.). Vol. 5250. Springer Verlag, Berlin Heidelberg, 3--37.

Digital Library

[14]

N. Creignou and B. Zanuttini. 2006. A complete classification of the complexity of propositional abduction. SIAM J. Comput. 36, 1 (2006), 207--229.

Digital Library

[15]

P. M. Dung. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77, 2 (1995), 321--358.

Digital Library

[16]

T. Eiter and G. Gottlob. 1995. The complexity of logic-based abduction. J. ACM 42, 1 (1995), 3--42.

Digital Library

[17]

D. Geiger. 1968. Closed systems of functions and predicates. Pacific J. Math. 27, 1 (1968), 95--100.

[18]

R. Hirsch and N. Gorogiannis. 2010. The complexity of the warranted formula problem in propositional argumentation. J. Log. Comput. 20 (2010), 481--499.

Digital Library

[19]

P. G. Jeavons. 1998. On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200 (1998), 185--204.

Digital Library

[20]

G. Nordh and B. Zanuttini. 2008. What makes propositional abduction tractable. Artif. Intell. 172, 10 (2008), 1245--1284.

Digital Library

[21]

C. Papadimitriou and D. Wolfe. 1988. The complexity of facets resolved. J. Comput. Syst. Sci. 37, 1 (1988), 2--13.

Digital Library

[22]

C. H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley.

[23]

S. Parsons, M. Wooldridge, and L. Amgoud. 2003. Properties and complexity of some formal inter-agent dialogues. J. Log. Comput. 13, 3 (2003), 347--376.

[24]

E. Post. 1941. The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5 (1941), 1--122.

[25]

H. Prakken and G. Vreeswijk. 2002. Logical Systems for Defeasible Argumentation. In Handbook of Philosophical Logic, D. Gabbay (Ed.). Kluwer.

[26]

T. J. Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the 10th Symposium on Theory of Computing. ACM, 216--226.

Digital Library

[27]

H. Schnoor and I. Schnoor. 2008. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, N. Creignou, Ph. G. Kolaitis, and H. Vollmer (Eds.). Vol. 5250. Springer-Verlag, Berlin Heidelberg, 229--254.

Digital Library

Cited By

Creignou NOlive FSchmidt JWilliams BChen YNeville J(2023)Complexity of reasoning with cardinality minimality conditionsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25507(3932-3940)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25507
Mahmood YMeier ASchmidt J(2023)Parameterized Complexity of Logic-based Argumentation in Schaefer’s FrameworkACM Transactions on Computational Logic10.1145/358249924:3(1-25)Online publication date: 31-Jan-2023
https://dl.acm.org/doi/10.1145/3582499
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Show More Cited By

Recommendations

Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. ...
The complexity of primal logic with disjunction

We investigate the complexity of primal logic with disjunction according to the Kripke semantics as defined in 1] and the quasi-boolean semantics as defined in 2]. We show that the validity problem is coNP -complete, even for variable-free sequents. For ...
Logic-based argumentation with existential rules

In this paper we are interested in the use of argumentation for handling inconsistency in inconsistent knowledge bases expressed with existential rules. We propose an instantiation of an argumentation framework and demonstrate it is coherent, relatively ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 15, Issue 3

July 2014

250 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/2648783

Editor:
Dale Miller
INRIA Saclay, France

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2014

Accepted: 01 January 2014

Revised: 01 December 2013

Received: 01 April 2013

Published in TOCL Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Austrian Science Fund
National Graduate School in Computer Science (CUGS)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
144
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Creignou NOlive FSchmidt JWilliams BChen YNeville J(2023)Complexity of reasoning with cardinality minimality conditionsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25507(3932-3940)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25507
Mahmood YMeier ASchmidt J(2023)Parameterized Complexity of Logic-based Argumentation in Schaefer’s FrameworkACM Transactions on Computational Logic10.1145/358249924:3(1-25)Online publication date: 31-Jan-2023
https://dl.acm.org/doi/10.1145/3582499
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Mahmood YMeier ASchmidt J(2020)Parameterized complexity of abduction in Schaefer’s frameworkJournal of Logic and Computation10.1093/logcom/exaa079Online publication date: 29-Dec-2020
https://doi.org/10.1093/logcom/exaa079

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents