On the Complexity of Probabilistic Abstract Argumentation Frameworks
Bettina Fazzinga, Sergio Flesca, Francesco Parisi · ACM Transactions on Computational Logic · 2015
Probabilistic abstract argumentation combines Dung’s abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is anextensionaccording to a given semantics. We focus on the most popular semantics (i.e.,admissible,stable,complete,grounded,preferred,ideal-set,ideal,stage, andsemistable) and show the following dichotomy result: computing the probability that a set of arguments is an extension is eitherFPorFP#P-complete depending on the semantics adopted. Our polynomial-time results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.