Tech Reports

ULCS-08-015

The Computational Complexity of Ideal Semantics

Paul E. Dunne

Abstract

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.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.