# Strong Backdoors for Default Logic

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2016.

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

- [Complexity of Faceted Explanations in Propositional Abduction](https://mlsanity.com/paper/2507.14962/) (2025)

## Abstract (arXiv)

In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, identity). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-DP2 , or in para-NP, depending on the target class.