Summary
Sometimes, you can explain something in many ways, but it’s hard to pick the right explanation from what you observe. The authors study a type of logical reasoning called Horn abduction with rules and constraints, looking at which pieces of information you must observe so that an explanation can be found and uniquely selected. They identify conditions when observations are enough to guarantee a sensible explanation across all scenarios, and show that picking these observations can be very complex. Their results connect how to choose what to observe with how hard it is to explain something and how complex the information you store is.
What this means in practice
- •For knowledge representation engineers: Design systems that select critical observations ensuring explanations can be found and distinguished in complex logical models.
- •For diagnostic system developers: Determine minimal sensor sets needed to guarantee unique fault explanations under system constraints.
A theory result. No direct application yet.
Abstract
An explanation may exist in every complete context yet be impossible to select from the information observed. We study this distinction in finite propositional Horn abduction with integrity constraints. Observations are sufficient when each report admits one hypothesis set that is consistent and entails the manifestation in every compatible context. We characterize sufficiency by minimal context families with no common explanation. Their variable spans form a canonical hypergraph whose transversals are exactly the sufficient observation sets. The characterization recovers classical discernibility for unique explanations and supports composition across independent components. Minimal obstructions have unbounded cardinality even for acyclic rules, while rectangular explanation families admit a tight bound given by their largest choice domain. With circuit-defined contexts, sufficiency is $Π_3^P$-complete and selecting at most $k$ observable variables is $Σ_4^P$-complete, already for unrestricted contexts and acyclic rules. The selection reduction makes observation choices enforce globally fixed existential commitments. Explicit contexts reduce both tasks to NP-complete problems; tabulated explanation families make sufficiency polynomial. These results connect explanatory choice, information requirements, and representation cost.