Abstract
Abstract Argumentation Frameworks (AFs) typically treat arguments as atomic entities. In many real-world scenarios, however, arguments are merely vehicles for claims, and multiple distinct arguments may support the same conclusion. This paper investigates the computational implications of shifting focus from arguments to claims. By introducing Claim-augmented Argumentation Frameworks (CAFs), the authors provide a comprehensive complexity analysis of core reasoning tasks. The results show that this claim-centric perspective often increases the complexity of problems like verification and skeptical acceptance, though tractability can be recovered through structural constraints and parameterized complexity.
Introduction: From Arguments to Claims
In formal argumentation, the standard model is the Abstract Argumentation Framework (AF), represented as a directed graph where nodes are arguments and edges are attacks. Traditional research focuses on determining which sets of arguments (extensions) are "acceptable" under various semantics. However, this argument-centric view often fails to capture the needs of end-users in fields like legal reasoning or AI logic programming. In these contexts, the specific argument used is often less important than the claim it supports. For instance, multiple different lines of reasoning might all lead to the claim "The defendant is innocent."
To bridge this gap, the authors introduce the Claim-augmented Argumentation Framework (CAF). A CAF extends a standard AF by adding a labeling function that maps each argument to a specific claim. This many-to-one mapping introduces a new layer of complexity: a claim is considered supported if any argument supporting it is part of an extension.
Computational Challenges
The shift to a claim-centric view significantly alters the computational landscape. The authors analyze four primary decision problems across seven semantics (stable, preferred, grounded, etc.):
- Credulous Acceptance (Cred): Is a claim supported by at least one extension?
- Skeptical Acceptance (Skept): Is a claim supported by every extension?
- Verification (Ver): Does a given set of claims correspond exactly to the claims supported by some extension?
- Non-Empty Extension (NEmpty): Does there exist an extension supporting at least one claim?
The most striking result is the Verification Penalty. In standard AFs, verifying if a set of arguments constitutes an extension is typically a polynomial-time task (in P). In CAFs, verifying a set of claims becomes NP-complete for most semantics. This jump occurs because one must "guess" which specific combination of arguments produced the target set of claims. Similarly, skeptical acceptance under naive semantics jumps from P to coNP-complete.
Identifying Tractable Sub-problems
To mitigate these complexity hurdles, the paper explores two main avenues: structural constraints and parameterized complexity.
Well-formed Frameworks
The authors define "well-formed" CAFs, where arguments supporting the same claim are required to attack the same set of targets. This property is not just a mathematical convenience; it reflects how arguments are typically constructed from underlying knowledge bases. In well-formed frameworks, the complexity of verification often drops back to P, suggesting that the inherent "hardness" of claim-centric reasoning stems from "messy" claim assignments that lack logical consistency.
Parameterized Complexity
Even when problems remain hard in the general case, they may be solvable efficiently if the underlying graph structure is "simple." The authors apply tools from parameterized complexity, specifically tree-width and a novel incidence tree-width. They prove that many problems become Fixed-Parameter Tractable (FPT) when these structural parameters are low, providing a path for practical implementation in complex domains.
Summary of Results
The following table highlights the complexity shifts between standard AFs and the new claim-centric CAF model.
| Problem | Standard AF | General CAF | Well-formed CAF |
|---|---|---|---|
| Verification (Ver) | In P | NP-c | In P (mostly) |
| Skeptical (Naive) | In P | coNP-c | coNP-c |
Note: Bold text indicates a significant increase in computational complexity compared to standard AFs.
Conclusion
This research provides the first comprehensive complexity map for claim-centric abstract argumentation. While the transition from arguments to claims introduces significant computational overhead, the identification of "well-formed" structures and the use of structural parameters offer promising ways to manage this complexity. Future work may extend this model to account for relationships between claims themselves, such as contradictions or logical entailment, further narrowing the gap between abstract models and real-world human debate.
Summary updated