The complexity of logic-based abduction

TLDR

Abduction is an important form of nonmonotonic reasoning that seeks explanations for observed symptoms, and in logic-based abduction the application domain is described by a logical theory with candidates evaluated under minimality criteria such as subset‑minimality, cardinality, weight, or prioritization. The paper aims to analyze the complexity of decision and search problems in logic‑based abduction on propositional theories. The authors perform a comprehensive complexity analysis of these problems. The results show that abduction is harder than deduction, with basic forms of abduction yielding decision problems complete for second‑level polynomial hierarchy classes, and prioritization raising complexity to the third level in some cases.

Abstract

Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based abduction . Candidates for abductive explanations are usually subjected to minimality criteria such as subset-minimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases.