Credulous and skeptical acceptability in probabilistic abstract argumentation: complexity results

摘要

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 an argument is credulously or skeptically acceptable according to a given semantics. Specifically, we focus on the most popular semantics (i.e., admissible, stable, semi-stable, complete, grounded, preferred, ideal, ideal-set), and show that computing the probability that an argument is credulously or skeptically accepted is FP#P -complete independently from the adopted semantics, in the cases when computing it is not trivial (i.e., when skeptical acceptance is assumed under the admissible and ideal-set semantics).