Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the representation problem in propositional abduction, focusing on whether a given set of explanations can represent other explanations based on their symmetric difference. The authors classify the complexity of this problem, revealing that while many cases remain intractable, the complexity increase compared to classical abduction is often less severe than anticipated. Additionally, they explore parameterized complexity, uncovering new tractable and hard cases, and highlight a novel connection between coding theory and non-monotonic reasoning that could enhance understanding of solution spaces.
The complexity of representing explanations in propositional abduction is less daunting than expected, revealing surprising tractability in certain cases.
The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an influx of results asking more refined questions about the solution space rather than only individual solutions. For example, we might be interested in finding two solutions that are sufficiently far from each other (diverse solutions) in the solution space. In this paper we consider a related representation question where we ask if a given set of explanations S can represent any other explanation (that is, whether their symmetric difference is smaller than a given k). We first study this problem from a classical complexity perspective and obtain a complete classification. While only a handful of cases are tractable, the increase in complexity compared to classical abduction is often smaller than expected. We then study the parameterized complexity for several parameters and obtain new tractable and hard cases. Interestingly, a full parameterized complexity classification would require resolving the parameterized complexity of the covering radius problem from coding theory. To the best of our knowledge, no useful relationship between coding theory and non-monotonic reasoning has previously been established, but such connections seemingly become important when asking more complex questions about solution spaces.