On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks

Sarah Alice Gaggl, Sebastian Rudolph, Hannes StrassIJCAI 2015

Abstract

Abstract Dialectical Frameworks (ADFs) extend standard argumentation frameworks by allowing for arbitrary Boolean acceptance conditions. This paper presents the first exhaustive complexity analysis of "naive-based" semantics for ADFs, including conflict-free, naive, stage, and $nai_2$ semantics. We demonstrate that these semantics are computationally more demanding than their counterparts in standard argumentation theory, frequently reaching the third level of the polynomial hierarchy.

Introduction

In artificial intelligence, Abstract Argumentation Frameworks (AFs) are a standard formalism for modeling disputes. However, AFs are limited in their ability to represent "support" or complex logical conditions. Abstract Dialectical Frameworks (ADFs) were introduced to overcome these limitations by allowing each statement to have a flexible acceptance condition. While the complexity of standard ADF semantics (e.g., preferred, stable) has been established, naive-based semantics—valued for their handling of circular arguments—remained unmapped.

Problem Statement

The research addresses the computational complexity of four primary reasoning tasks across naive-based semantics ($\sigma \in \{cfi, nai, stg, nai_2\}$):

  1. Verification ($Ver_\sigma$): Determining if a given interpretation is a valid model under semantics $\sigma$.
  2. Existence ($Exists_\sigma$): Determining if a non-trivial model exists.
  3. Credulous Entailment ($Cred_\sigma$): Determining if a statement is true (or false) in at least one model.
  4. Sceptical Entailment ($Scept_\sigma$): Determining if a statement is true (or false) in all models.

Methods

The authors categorized these tasks using traditional computational complexity theory. Hardness results were established through reductions from Quantified Boolean Formulas (QBFs) and problems within the Boolean hierarchy. This approach allowed for a fine-grained classification of problems between NP and the third level of the polynomial hierarchy.

Key Insights

  • The "Naive" Irony: Despite their name, naive-based semantics in ADFs are significantly harder than in AFs. While many AF tasks are in P or NP, ADF tasks often jump to the second or third levels of the polynomial hierarchy.
  • Truth vs. Falsity Asymmetry: A rare gap was discovered in naive semantics: checking if a statement is false in all models ($\Pi^P_3$) is harder than checking if it is true ($\Pi^P_2$).
  • Source of Complexity: This asymmetry stems from the definition of "conflict-freeness" in ADFs. Proving a statement true requires a satisfiability check, while proving it false requires an unsatisfiability check, creating a ripple effect in higher-level semantics.

Key Results

The comprehensive complexity map is summarized in the table below. Notably, for stage and $nai_2$ semantics, both credulous and sceptical reasoning are complete for the third level of the polynomial hierarchy ($\Sigma^P_3$ and $\Pi^P_3$, respectively).

Complexity of reasoning tasks for naive-based ADF semantics.

Conclusion

The high complexity of naive-based semantics poses significant challenges for practical implementation. Future work should focus on identifying "amenable fragments" of ADFs, such as bipolar ADFs, where these problems may be more tractable. Additionally, developing efficient encodings for modern solvers (ASP or QBF) remains a priority for applying these semantics to real-world argumentation tasks.

Summary updated

BibTeX
@inproceedings{gaggl2015computational,
  author = {Sarah Alice Gaggl and Sebastian Rudolph and Hannes Strass},
  title = {{On the Computational Complexity of Naive-Based Semantics for Abstract Dialectical Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure