Complexity of Verification in Incomplete Argumentation Frameworks
Authors: Dorothea Baumeister, Daniel Neugebauer, Jörg Rothe, Hilmar Schadrack
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result shows that the complexity of verifying the preferred semantics rises from co NPto Σp 2-completeness when allowing uncertainty about either attacks or arguments, or both.We assume the reader to be familiar with the complexity classes of the polynomial hierarchy, in particular, P, NP, co NP, and Σp 2 = NPNP, as well as the concepts of hardness and completeness. |
| Researcher Affiliation | Academia | Dorothea Baumeister, Daniel Neugebauer, J org Rothe, Hilmar Schadrack Institut f ur Informatik Heinrich-Heine-Universit at D usseldorf 40225 D usseldorf, Germany |
| Pseudocode | Yes | Definition 15. Let IAF = A, A?, R, R? be an incomplete argumentation framework and S A A? be a set of arguments in IAF. The ungrounded completion IAF ungr S of IAF for S is obtained by the following algorithm. 1. Let R0 = R {(a, b) R? | b S}. 2. Let G0 = , A? 0 = A?, IAF 0 = A, A? 0, R0 , and i = 0. 3. Let Maxi be the maximal completion of IAF i and let Xi S be the set of arguments in S that are defended by Gi in Maxi, i.e., Xi = FMaxi(Gi) S. Add the definite arguments in Xi to Gi and exclude the possible arguments in Xi from the framework, i.e., Gi+1 = Gi (Xi \ A?), A? i+1 = A? i \ Xi, and Ri+1 = Ri|A A? i+1. Set i i + 1. 4. Repeat the previous step until Gi = Gi 1. 5. The ungrounded completion of IAF for S is IAF ungr S = Aungr S , R|Aungr S with Aungr S = A A? i. |
| Open Source Code | No | The paper does not contain any statement about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve empirical experiments with datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not describe experimental validation with dataset splits. |
| Hardware Specification | No | This is a theoretical paper; no specific hardware used for experiments is mentioned. |
| Software Dependencies | No | This is a theoretical paper and does not describe software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This is a theoretical paper and does not provide details on experimental setup, hyperparameters, or system-level training settings. |