Strong Backdoors for Default Logic
This work addresses computational complexity challenges in default logic for AI and theoretical computer science researchers, representing an incremental extension of backdoor concepts from other logic frameworks.
The paper tackles the problem of analyzing computational complexity in Reiter's propositional default logic by introducing a notion of backdoors and studying their structural properties. It shows that backdoor detection is fixed-parameter tractable for target classes like cnf, horn, krom, monotone, and identity, while backdoor evaluation varies from fixed-parameter tractable to para-DP2 or para-NP depending on the class.
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.