Computational complexity of flat and generic Assumption-Based Argumentation, with and without probabilities

摘要

Reasoning with probabilistic information has recently attracted considerable attention in argumentation, and formalisms of Probabilistic Abstract Argumentation (PAA), Probabilistic Bipolar Argumentation (PBA) and Probabilistic Structured Argumentation (PSA) have been proposed. These foundational advances have been complemented with investigations on the complexity of some approaches to PAA and PBA, but not to PSA. We study the complexity of an existing form of PSA, namely Probabilistic Assumption-Based Argumentation (PABA), a powerful, implemented formalism which subsumes several forms of PAA and other forms of PSA. Specifically, we establish membership (general upper bounds) and completeness (instantiated lower bounds) of reasoning in PABA for the class FP#P (of functions with a #P-oracle for counting the solutions of an NP problem) with respect to newly introduced probabilistic verification, credulous and sceptical acceptance function problems under several ABA semantics. As a by-product necessary to establish PABA complexity results, we provide a comprehensive picture of the ABA complexity landscape (for both flat and generic, possibly non-flat ABA) for the classical decision problems of verification, existence, credulous and sceptical acceptance under those ABA semantics.