Complexity boundaries identified for reasoning in infinite argument systems

Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

Artificial IntelligenceLogic in Computer Science

Summary

Argumentation frameworks help computers reason when information is complicated or conflicting. The researchers studied how hard it is to decide various questions about these frameworks when the structures are infinite but follow certain computability rules. They discovered exactly which problems become simpler and which remain very complex depending on the type of reasoning used. This helps clarify when infinite argument systems can be managed more easily by computers and when complex logic still makes reasoning difficult.

What this means in practice

  • For software developers: Design software that manages infinite but computably bounded arguments by knowing which reasoning tasks are computationally feasible.
  • For automated reasoning engineers: Improve AI reasoning systems by targeting grounded semantics for simpler decision problems and recognizing limits of preferred semantics in infinite cases.

A theory result. No direct application yet.

Authors

Jinfan Xu, Jieting Luo

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 ($Σ_1^1$ or $Π_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 $Σ_1^0$-complete. We show that non-empty existence is also $Σ_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 $Π_1^0$-c and $\NE_{\pref}$ is $Σ_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $Π_1^1$ and $\UniPref$ in $Σ_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.