Backdoors to Abduction
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 1046-1051.
Abstract
Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abduction is of high computational complexity; even propositional Abduction is Σ2P-complete and thus harder than NP and coNP. This complexity barrier rules out the existence of a polynomial transformation to propositional satisfiability (SAT). In this work we use structural properties of the Abduction instance to break this complexity barrier. We utilize the problem structure in terms of small backdoor sets. We present fixed-parameter tractable transformations from Abduction to SAT, which make the power of today's SAT solvers available to Abduction.
@inproceedings{ijcai2013p159,
title = {Backdoors to Abduction},
author = {Pfandler, Andreas and Rümmele, Stefan and Szeider, Stefan},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {1046--1051},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/159},
}
TY - CPAPER TI - Backdoors to Abduction AU - Pfandler, Andreas AU - Rümmele, Stefan AU - Szeider, Stefan T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 1046 EP - 1051 UR - https://ijcai.org/proceedings/2013/159 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
