Title: On the complexity of inconsistency measurement
Authors: Thimm, Matthias 
Wallner, Johannes 
Category: Original Research Article
Issue Date: Oct-2019
Thimm, M., & Wallner, J. (2019). On the complexity of inconsistency measurement. Artificial Intelligence, 275, 411–456. https://doi.org/10.34726/1801
Journal: Artificial Intelligence 
ISSN: 0004-3702
We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic.
Keywords: Inconsistency measurement; Computational Complexity
DOI: 10.1016/j.artint.2019.07.001
DOI: 10.34726/1801
Organisation: E192 - Institut für Logic and Computation 
License: CC BY-NC-ND 4.0 CC BY-NC-ND 4.0
Publication Type: Article
Appears in Collections:Article

Files in this item:

Page view(s)

checked on Nov 28, 2021


checked on Nov 28, 2021

Google ScholarTM


This item is licensed under a Creative Commons License Creative Commons