Tech Reports


The Computational Complexity of Ideal Semantics

Paul E. Dunne


We analyse the computational complexity of the recently proposed ideal semantics within both abstract argumentation frameworks (AFs) and assumption-based argumentation frameworks (ABFs). It is shown that while typically less tractable than credulous admissibility semantics, the natural decision problems arising with this extension-based model can, perhaps surprisingly, be decided more efficiently than sceptical preferred semantics. In particular the task of finding the unique ideal extension is easier than that of deciding if a given argument is accepted under the sceptical semantics. We provide efficient algorithmic approaches for the class of bipartite argumentation frameworks. Finally we present a number of technical results which offer strong indications that typical problems in ideal argumentation are complete for the class P^{C}_{||} of languages decidable by polynomial time algorithms allowed to make non-adaptive queries to a C oracle, where C is an upper bound on the computational complexity of deciding credulous acceptance: C=NP for AFs and logic programming (LP) instantiations of ABF; C=Sigma_{2}^{p} for ABFs modelling default theories.

[Full Paper]