Complexity of logic-based argumentation in Schaefer's framework

摘要

We consider logic-based argumentation in which an argument is a pair (Φ,a), where the support Φ is a minimal consistent set of formulae of a given knowledge base that entails the formula a. We study the complexity of two different problems: the existence of a support and the verification of the validity of an argument. When arguments are given in the full language of propositional logic these problems are computationally costly tasks, they are respectively∑~p_2- and DP-complete. We study these problems in Schaefer's famous framework. We consider the case where formulae are taken from a class of formulae in generalized conjunctive normal form. This means that the propositional formulae considered are conjunctions of constraints taken from a fixed finite 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_2-complete. We also obtain a dichotomous classification, P or DP-complete, for the verification problem.