TY - GEN
T1 - Explainability via Short Formulas: the Case of Propositional Logic with Implementation
AU - Jaakkola, Reijo
AU - Janhunen, Tomi
AU - Kuusisto, Antti
AU - Feyzbakhsh Rankooh, Masood
AU - Vilander, Miikka
PY - 2022/9/5
Y1 - 2022/9/5
N2 - We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.
AB - We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.
KW - Explainability
KW - Answer Set Programming
KW - satisfiability checking
KW - Computational complexity
M3 - Conference contribution
VL - 3281
T3 - CEUR workshop proceedings
SP - 64
EP - 77
BT - Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning HYDRA} 2022 and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion RCRA 2022 co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning LPNMR 2022, Genova Nervi, Italy, September 5, 2022
PB - CEUR-WS
T2 - RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Y2 - 5 September 2022 through 5 September 2022
ER -