Tech Reports

ULCS-07-008

The Computational Complexity of Ideal Semantics I: Abstract Argumentation Frameworks

Paul E. Dunne

Abstract

We analyse the computational complexity of the recently proposed ideal semantics within abstract argumentation frameworks. 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 admissibility semantics. In particular the task of finding the unique maximal 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 $mbox{{sc p}}^{mbox{{sc np}}}_{||}$: languages decidable by polynomial time algorithms allowed to make non-adaptive queries to an NP oracle.

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.