Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility
AbstractWe study the computational complexity of abstract argumentation semantics based on weak admissibility, a recently introduced concept to deal with arguments of self-defeating nature. Our results reveal that semantics based on weak admissibility are of much higher complexity (under typical assumptions) compared to all argumentation semantics which have been analysed in terms of complexity so far. In fact, we show PSPACE-completeness of all non-trivial standard decision problems for weak-admissible based semantics. We then investigate potential tractable fragments and show that restricting the frameworks under consideration to certain graph-classes significantly reduces the complexity. As a strategy for implementation we also provide a polynomial-time reduction to DATALOG with stratified negation.
How to Cite
Dvořák, W., Ulbricht, M., & Woltran, S. (2021). Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6288-6295. https://doi.org/10.1609/aaai.v35i7.16781
AAAI Technical Track on Knowledge Representation and Reasoning