## Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence.(English)Zbl 1478.68352

Summary: The complexity of the probabilistic counterparts of the classical verification and acceptance problems is investigated over Probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than that considered in the current literature, where the complexity has been characterized only under the assumption of independence between arguments/defeats. The complexity of the problems is shown to range from FP to $$\mathrm{FP}^\mathrm{\#P}$$-complete, with $$\mathrm{FP}^{\|\mathrm{NP}}$$-complete cases, depending on the semantics of the extensions, the representation paradigm used for encoding the prAAF, and the imposed correlations between arguments/defeats, thus providing a thorough analysis of the sensitivity to several aspects. In this regard, in order to allow the study of the impact of different forms of correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set descriptors and world-set sets for representing probabilities, and it allows the correlations to be easily and explicitly expressed. Interestingly, the introduction of gen is shown to be also a standalone contribution as a powerful representation paradigm for prAAFs, owing to its high expressiveness, compactness, and the possibility to support user-friendly mechanisms for defining correlations.

### MSC:

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

### Keywords:

probabilistic abstract argumentation; complexity

### Software:

Dungine; ASPARTIX
Full Text: