Abstract
Formal AI systems traditionally represent knowledge using logical formulas. This paper demonstrates that for certain classes of information, a model-based representation is significantly more compact and enables faster reasoning than traditional formula-based approaches. The central innovation is the representation of large sets of models through a subset of "characteristic models." Focusing on Horn theories, we show that these theories can often be exactly represented by an exponentially smaller set of characteristic models. Furthermore, while deduction remains efficient, abduction—an NP-complete problem in Horn logic—becomes solvable in polynomial time when using this model-based framework.
The Problem: The Complexity of Rule-Based Logic
In formal AI, knowledge is typically encoded as logical formulas or rules. While expressive, this approach faces two significant hurdles. First, reasoning with formulas is computationally expensive. Even in relatively simple Horn theories (rules with at most one positive literal), tasks such as abduction—finding a minimal set of assumptions to explain an observation—are NP-complete. Second, maintaining large, consistent rule bases is a complex task for human developers.
This research explores a model-based alternative: instead of storing rules, the system stores the "cases" or truth assignments (models) that satisfy those rules. Because the total number of models is often too large to store, the challenge lies in identifying a small, "characteristic" subset that captures the entire theory without loss of information.
The Model-Based Approach
The authors focus on Horn theories, which possess a unique mathematical property: the intersection of any two models of a Horn theory is also a model of that theory. This allows for the definition of a "basis" known as characteristic models.
Characteristic models are the minimal set from which all other satisfying models in the theory can be generated via bitwise intersections. This approach functions as a form of "knowledge compilation." While identifying these models (the offline phase) may be computationally intensive, the resulting "online" reasoning becomes significantly faster.
Key Insights and the "Size Paradox"
A common assumption in logic is that formulas serve as a compressed version of models. This paper identifies a "Size Paradox," proving that for some theories, the most efficient formula-based representation is exponentially larger than the set of characteristic models. For example, the authors prove the existence of Horn theories with $O(n^2)$ characteristic models that would require $O(2^n)$ clauses to represent as formulas.
This shift in representation fundamentally changes the complexity of reasoning:
- Deduction: Determining if a fact follows from the models is proven to be linear time $O(|M| + |\alpha|)$, where $|M|$ is the size of the model set. This matches the efficiency of formula-based methods.
- Abduction: In rule-based systems, abduction requires searching an exponential space. With characteristic models, the problem becomes polynomial time $O(|M|^2 \cdot |A|^3)$, where $A$ is the set of possible assumptions. This is achieved by iterating through the models to find a satisfying instance and then greedily minimizing assumptions.
Conclusion and Future Directions
By providing a formal mathematical bridge to Case-Based Reasoning (CBR), this work suggests that "reasoning by examples" is more than a heuristic; it is a formally superior method for specific logical structures.
While the current scope is limited to Horn theories and the initial "compilation" of models can be slow, the implications for high-speed query systems are significant. Future work aims to extend these concepts to more expressive logics and explore the possibility of AI systems learning characteristic models directly from empirical data, bypassing the need for human-written rules entirely.
Summary updated