Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Irina TrubitsynaAAAI 2024 · DOI

TL;DR

This paper delves into the computational complexity of reasoning within "Epistemic Argumentation Frameworks" (EAFs), which model how agents reason about beliefs and knowledge. The authors introduce a new framework, Labeled Constrained AF (LCAF), and show that EAFs, despite their expressive power, have the same computational complexity as LCAF, offering a unified understanding of reasoning under uncertainty.

What Problem Does This Paper Address?

Formal argumentation systems, like Dung's Abstract Argumentation Framework (AF), are powerful tools for modeling disputes and reasoning about conflicting information. However, these systems often struggle to capture nuanced aspects of an agent's beliefs and knowledge. To address this, researchers have developed extensions like Incomplete AF (iAF), which handles uncertain arguments and attacks, and Constrained AF (CAF), which incorporates explicit constraints on acceptable arguments.

A more recent extension, Epistemic AF (EAF), introduces epistemic constraints using modal operators like "K" (believes) and "M" (possibly believes). While the complexity of reasoning in AF, iAF, and CAF has been studied, the computational complexity of EAF has remained an open question. This paper aims to fill that gap by investigating the complexity of credulous (is there any scenario where an argument is accepted?) and skeptical (is an argument accepted in all scenarios?) acceptance in EAFs. It also explores the relationships between EAF, iAF, and a new framework called Labeled Constrained AF (LCAF).

Methods

The authors introduce Labeled Constrained AF (LCAF), a framework that extends AFs with propositional formulas built over labeled arguments (e.g., "argument 'a' is accepted"). LCAF is a restricted form of EAF where modal operators are disallowed. This allows them to analyze the complexity of reasoning without the added layer of epistemic modalities.

They then establish key relationships:

  • LCAF generalizes iAF: They show that reasoning problems in iAF can be reduced to those in LCAF. This means LCAF is at least as expressive as iAF.
  • EAF and LCAF have the same complexity: Despite EAF's ability to use modal operators (K and M) for more natural modeling of beliefs, its computational complexity for credulous and skeptical acceptance turns out to be the same as LCAF. This is a significant finding, suggesting that the added expressiveness of modal operators doesn't increase the inherent computational difficulty of these reasoning tasks.

The paper analyzes the complexity of credulous and skeptical acceptance for various semantics (grounded, complete, preferred, stable, semi-stable) within these frameworks, using standard complexity classes like P, NP, coNP, Σ, and Π.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of computational complexity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • EAF's expressiveness doesn't increase complexity: A major "aha moment" is that EAF, with its powerful modal operators for expressing beliefs, has the same computational complexity as LCAF, which lacks these operators. This implies that while EAF allows for more intuitive modeling of domain knowledge, it doesn't inherently make reasoning harder.
  • LCAF as a bridge: The introduction of LCAF serves as a crucial stepping stone. By analyzing LCAF first, the authors can then relate it to both iAF and EAF, providing a unified perspective on reasoning under uncertainty and belief.
  • Unified complexity for EAF and LCAF: The paper demonstrates that the complexity of credulous and skeptical acceptance in EAF is equivalent to that in LCAF across different semantics. This is a strong theoretical result that simplifies our understanding of these epistemic reasoning systems.
  • EAF generalizes iAF: The reduction from iAF to LCAF, and the fact that LCAF is a special case of EAF, means EAF can also encode iAF reasoning problems. This positions EAF as a potentially unifying framework for various forms of argumentation with uncertainty and belief.

Key Results

The paper provides detailed complexity results for credulous (CA) and skeptical (SA) acceptance in LCAF and EAF across different semantics:

For LCAF and EAF: * Grounded semantics (gr): CA and SA are in P (polynomial time). * Complete (co) and Stable (st) semantics: CA is NP-complete, and SA is coNP-complete. * Preferred (pr) and Semi-stable (sst) semantics: CA is Σ-complete, and SA is Π-complete.

These results are summarized in Table 1 of the paper. Notably, the complexity for EAF is shown to be identical to that of LCAF.

Limitations and Future Work

  • Open problem: EAF to LCAF reduction: While the paper shows that EAF and LCAF have the same complexity, a direct polynomial-time reduction from EAF to LCAF is still an open problem.
  • More general epistemic constraints: The authors suggest future work on handling more complex epistemic constraints, such as those involving aggregate conditions (e.g., "the agent believes at least n arguments from set S are accepted").
  • Structured argumentation: Extending epistemic constraints to structured argumentation formalisms is another avenue for future research.
  • Incremental techniques: Investigating incremental methods for recomputing EAF semantics after updates to the framework or constraints is proposed.
  • Empirical evaluation: While the paper focuses on theoretical complexity, future work could involve developing and evaluating algorithmic solutions, potentially using SAT-based CEGAR or mapping EAF to Epistemic ASP (EASP).

Summary updated

BibTeX
@inproceedings{alfano2024complexity,
  author = {Gianvincenzo Alfano and Sergio Greco and Francesco Parisi and Irina Trubitsyna},
  title = {{Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28910},
}

Loading related content...

Figure