Complexity Classifications for Logic-Based Argumentation

DOI10.1145/2629421MaRDI QIDQ2946726zbMATH OpenOpenAlexWikidataFDO

Authors Nadia Creignou, Uwe Egly, Johannes Schmidt

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitylogic-based argumentationgeneralized satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Abstract: We consider logic-based argumentation in which an argument is a pair (Fi,al), where the support Fi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by De) that entails the claim al (a formula). We study the complexity of three central problems in argumentation: the existence of a support Fi ss De, the validity of a support and the relevance problem (given psi is there a support Fi such that psi ss Fi?). When arguments are given in the full language of propositional logic these problems are computationally costly tasks, the validity problem is DP-complete, the others are SigP2-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 build upon a fixed finite set of Boolean relations Ga (the constraint language). We show that according to the properties of this language Ga, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or SigP2-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 SigP2-complete. These last two classifications are obtained by means of algebraic tools.

Recommendations

• Logics for complexity classes
• scientific article; zbMATH DE number 4103047
• Complexity-sensitive decision procedures for abstract argumentation
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
• scientific article; zbMATH DE number 3995647
• scientific article; zbMATH DE number 65760
• scientific article; zbMATH DE number 4114609
• Complexity of abstract argumentation under a claim-centric view
• Logical and schematic characterization of complexity classes

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1852916 (Why is no real title available?)
• A Complete Classification of the Complexity of Propositional Abduction
• A logic-based theory of deductive arguments
• Bases for Boolean co-clones
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Closed systems of functions and predicates
• Complexity classifications for propositional abduction in Post's framework
• Complexity classifications of Boolean constraint satisfaction problems
• Mathematical Foundations of Computer Science 2005
• On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games
• On the algebraic structure of combinatorial problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• Properties and Complexity of Some Formal Inter-agent Dialogues
• Structure identification of Boolean relations and plain bases for co-clones
• The complexity of facets resolved
• The complexity of logic-based abduction
• The complexity of satisfiability problems
• The complexity of the warranted formula problem in propositional argumentation
• What makes propositional abduction tractable

Cited in

(8)

• The complexity of the warranted formula problem in propositional argumentation
• Time complexity of constraint satisfaction via universal algebra
• Sets of Boolean connectives that make argumentation easier
• Algorithms for generating arguments and counterarguments in propositional logic
• Complexity-sensitive decision procedures for abstract argumentation
• Complexity of Possible and Necessary Existence Problems in Abstract Argumentation
• Logics in Artificial Intelligence
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework

This page was built for publication: Complexity Classifications for Logic-Based Argumentation

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