International Joint Conference on Artificial Intelligence · 2013 · 42 citations · 21 references
ComputingComputer ScienceMathematicsKnowledge RepresentationProbability TheoryUncertainty QuantificationArgumentationArgumentation TheoryFormal SemanticsUncertainty ReasoningUncertainty Representation#P-complete ProblemsAbstract ArgumentationComputational ArgumentationFormal ArgumentationPolynomial Time ComplexityPolynomial-time AlgorithmsProbabilistic LogicProbabilistic Semantics
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 an extension according to a given semantics. We focus on the most popular semantics (i.e., admissible, stable, complete, grounded, preferred, ideal), and show the following dichotomy result: computing the probability that a set of arguments is an extension is either PTIME or FP#P -complete depending on the semantics adopted. Our PTIME results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.
21
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
Argumentation in artificial intelligence
Trevor Bench‐Capon, Paul E. Dunne · Artificial Intelligence · 2007 · 804 citations