Complexity of Verification in Incomplete Argumentation Frameworks

Dorothea Baumeister, Daniel Neugebauer, Jörg Rothe, Hilmar Schadrack

AAAI 2018 pp. 1753-1760

doi:10.1609/AAAI.V32I1.11562 /aaai/2018/baumeister2018aaai-complexity/

Abstract

Abstract argumentation frameworks are a well-established formalism to model nonmonotonic reasoning processes. However, the standard model cannot express incomplete or conflicting knowledge about the state of a given argumentation. Previously, argumentation frameworks were extended to allow uncertainty regarding the set of attacks or the set of arguments. We combine both models into a model of general incompleteness, complement previous results on the complexity of the verification problem in incomplete argumentation frameworks, and provide a full complexity map covering all three models and all classical semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Sigma^p_2-completeness when allowing uncertainty about either attacks or arguments, or both.

PDF AAAI Semantic Scholar

Cite

Text

Baumeister et al. "Complexity of Verification in Incomplete Argumentation Frameworks." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11562

Markdown

[Baumeister et al. "Complexity of Verification in Incomplete Argumentation Frameworks." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/baumeister2018aaai-complexity/) doi:10.1609/AAAI.V32I1.11562

BibTeX

@inproceedings{baumeister2018aaai-complexity,
  title     = {{Complexity of Verification in Incomplete Argumentation Frameworks}},
  author    = {Baumeister, Dorothea and Neugebauer, Daniel and Rothe, Jörg and Schadrack, Hilmar},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {1753-1760},
  doi       = {10.1609/AAAI.V32I1.11562},
  url       = {https://mlanthology.org/aaai/2018/baumeister2018aaai-complexity/}
}