The Complexity Landscape of Claim-Augmented Argumentation Frameworks

Wolfgang Dvorák, Alexander Greßler, Anna Rapberger, Stefan WoltranAAAI 2021 · DOI

Introduction

Abstract Argumentation Frameworks (AFs), as proposed by Dung, provide a robust mathematical structure for modeling conflict between arguments. However, in practical applications, multiple arguments often converge on the same conclusion. Claim-Augmented Argumentation Frameworks (CAFs) address this by introducing a claim function that maps each argument to a specific conclusion. This paper provides a comprehensive complexity map for CAFs, specifically focusing on the distinction between inherited semantics and claim-level semantics.

Example of a Claim-Augmented Argumentation Framework (CAF) where arguments $a_1, a_2$ share claim $a$, and $b_1, b_2$ share claim $b$.

Problem Statement: Inherited vs. Claim-Level Semantics

There are two primary paradigms for evaluating CAFs:

  1. Inherited (i-semantics): Extensions are first identified at the argument level using standard AF semantics. The resulting sets of claims are then derived from these argument extensions.
  2. Claim-level (cl-semantics): The selection process—such as finding maximal conflict-free sets—is performed directly on the sets of claims.

While i-semantics are generally well-behaved, cl-semantics can lead to significantly higher computational costs. This research aims to map these complexities and solve the concurrence problem: determining when these two approaches yield identical results for a specific framework.

Methodology

The authors utilize formal complexity theory to establish upper and lower bounds for four fundamental reasoning tasks across various semantics (stable, naive, preferred, semi-stable, and stage):

  • Credulous Acceptance ($Cred$): Is a given claim supported by at least one extension?
  • Skeptical Acceptance ($Skept$): Is a given claim supported by all extensions?
  • Verification ($Ver$): Is a given set of claims a valid extension?
  • Non-emptiness ($NE$): Does the framework produce at least one non-empty set of claims?

To prove hardness, the authors construct elaborate reductions from known hard problems in the polynomial hierarchy, such as Boolean Satisfiability (SAT) and Quantified Boolean Formulas (QSAT). They also introduce specific translations ($Tr_1, Tr_2, Tr_3$) to show how one type of semantics can be reduced to another, helping establish tight complexity bounds.

Key Insights

  • The Complexity Jump: Shifting from argument-centric to claim-centric evaluation often increases the difficulty of reasoning problems. For instance, skeptical acceptance under naive semantics jumps from polynomial time (P) in standard AFs to $\Pi^P_2$-complete in the claim-level variant.
  • The "Naive" Surprise: For naive semantics, the claim-level variant is significantly harder than the inherited one. This is because maximizing over sets of claims requires navigating the underlying argument conflicts in a more complex way.
  • The Concurrence Challenge: Deciding if inherited and claim-level semantics coincide is remarkably difficult, reaching $\Pi^P_3$-completeness for semi-stable and stage semantics. This indicates that no simple structural heuristic can easily predict when these two methods will align.
  • Well-formedness as a Buffer: In "well-formed" CAFs—where all arguments supporting the same claim share the same attack targets—the complexity often reverts to the levels seen in standard AFs, providing a potential path for efficient implementation.

Results

The primary contribution of this work is a comprehensive classification of complexity bounds for claim-level semantics. As shown in the table below, these semantics frequently push problems into higher levels of the polynomial hierarchy, often moving from P or NP to $\Sigma^P_2$ or $\Pi^P_2$.

Complexity of reasoning problems for claim-level semantics ($cl\text{-}\sigma$). Note the prevalence of $\Sigma^P_2$-c and $\Pi^P_2$-c results compared to standard AFs.

Conclusion

This paper establishes that the order of operations in claim-augmented reasoning is a critical factor in computational feasibility. While claim-level semantics offer a more "claim-centric" view of argumentation, they come with a substantial complexity penalty. Future work will focus on developing practical solvers using Answer Set Programming (ASP) or SAT-based reductions to handle these high-complexity problems in real-world applications.

Summary updated

BibTeX
@inproceedings{dvorak2021complexity,
  author = {Wolfgang Dvorák and Alexander Greßler and Anna Rapberger and Stefan Woltran},
  title = {{The Complexity Landscape of Claim-Augmented Argumentation Frameworks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16782},
}
Figure