@article{Cyras:2021:10.1016/j.artint.2020.103449,
author = {Cyras, K and Heinrich, Q and Toni, F},
doi = {10.1016/j.artint.2020.103449},
journal = {Artificial Intelligence},
pages = {1--36},
title = {Computational complexity of flat and generic assumption-based argumentation, with and without probabilities},
url = {http://dx.doi.org/10.1016/j.artint.2020.103449},
volume = {293},
year = {2021}
}

Download

TY  - JOUR
AB  - 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.
AU  - Cyras,K
AU  - Heinrich,Q
AU  - Toni,F
DO  - 10.1016/j.artint.2020.103449
EP  - 36
PY  - 2021///
SN  - 0004-3702
SP  - 1
TI  - Computational complexity of flat and generic assumption-based argumentation, with and without probabilities
T2  - Artificial Intelligence
UR  - http://dx.doi.org/10.1016/j.artint.2020.103449
UR  - https://www.sciencedirect.com/science/article/pii/S000437022030196X?via%3Dihub
UR  - http://hdl.handle.net/10044/1/85195
VL  - 293
ER  - 

Download