Propositional Abduction is Almost Always Hard
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 534-538.
Abstract
Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. Applications of this process range from car configuration to medical diagnosis. We study here its computational complexity in the case where the application domain is described by a propositional theory built upon a fixed constraint language and the hypotheses and manifestations are described by sets of literals. We show that depending on the language the problem is either polynomial-time solvable, NP-complete, or ΣP 2 -complete. In particular, we show that under the assumption P6=NP, only languages that are affine of width 2 have a polynomial algorithm, and we exhibit very weak conditions for NP-hardness.
@inproceedings{ijcai2005p35,
title = {Propositional Abduction is Almost Always Hard},
author = {Nordh, Gustav and Zanuttini, Bruno},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {534--538},
year = {2005},
url = {https://ijcai.org/proceedings/2005/35},
}
TY - CPAPER TI - Propositional Abduction is Almost Always Hard AU - Nordh, Gustav AU - Zanuttini, Bruno T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 534 EP - 538 UR - https://ijcai.org/proceedings/2005/35 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
