Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

arXiv:2610.12008v1 Announce Type: new Abstract: Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy (Sigma_1^1 or Pi_1^1), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance (Cred), skeptical acceptance (Skep), extension existence (Ex), uniqueness (Uni), and non-empty existence (NE). For grounded semantics, credulous and skeptical acceptance are already known to be Sigma_1^0-complete. We show that non-empty existence is also Sigma_1^0-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, Cred_{pref} is shown to be in Pi_1^0-c and NE_{pref} is Sigma_2^0-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving Skep_{pref} in Pi_1^1 and UniPref in Sigma_2^1-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.

Source: arXiv cs.AI | 2026-10-09