The computational complexity of ideal semantics

摘要

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 admissibi-lity 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 and, finally, 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 abfs; C=Σ2p for abfs modelling default theories.