Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence

摘要

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 FP#P-complete, with FP‖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.