# Backdoors to Abduction

arXiv: https://arxiv.org/abs/1304.5961 · HTML: https://mlsanity.com/paper/1304.5961/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2013.

## Built on by (most cited first, 2 of 2)

- [Complexity of Faceted Explanations in Propositional Abduction](https://mlsanity.com/paper/2507.14962/) (2025)
- [Computational Short Cuts in Infinite Domain Constraint Satisfaction](https://mlsanity.com/paper/2211.10144/) (2022)

## Abstract (arXiv)

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 Sigma2P-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.