Abstract
Characteristic models offer a model-based alternative to traditional Horn expressions for representing knowledge. While these two representations are incomparable—each excelling at different reasoning tasks—the computational cost of translating between them is a critical factor in their practical application. This paper investigates the complexity of these translation problems, demonstrating that the tasks of computing characteristic models from a Horn expression and identifying a Horn expression from a set of models are computationally equivalent. Furthermore, these problems are shown to be equivalent to the decision problem of verifying whether a set of models correctly represents a given Horn expression. The study also establishes a significant link to the hypergraph transversal problem, providing a lower bound for the complexity of these AI tasks and highlighting parallels in relational database theory.
Introduction
In the field of Artificial Intelligence, the choice of knowledge representation significantly impacts the efficiency of reasoning. Horn formulas—conjunctions of clauses with at most one positive literal—are widely used because they allow for rapid deductive reasoning. However, for tasks such as abduction (finding explanations) or default reasoning, Horn formulas can be computationally expensive to manipulate.
An alternative approach is to represent the same knowledge using characteristic models, a specific subset of all satisfying assignments that can generate the entire set of models through intersection. While some tasks are easier with formulas, others are more efficient with models. This paper explores the computational feasibility of moving between these two representations to leverage the strengths of both.
Core Computational Problems
The paper formalizes three primary problems to map the complexity of these translations:
- Computing Characteristic Models (CCM): Given a Horn formula, find its set of characteristic models.
- Structure Identification (SID): Given a set of models, find the underlying Horn formula that represents them.
- Characteristic Models Identification (CMI): Given both a Horn formula and a set of models, decide if the set correctly and completely represents the formula.
The Equivalence of Translation and Decision
A central contribution of this research is the proof that the search problems (CCM and SID) are exactly as difficult as the decision problem (CMI). Through the use of polynomial reductions, the author demonstrates that if one can efficiently verify whether a set of models is correct, one can also generate that set in polynomial time (relative to the size of the output).
To prove this, the author utilizes a "substitution trick." By systematically fixing variables to specific truth values and using the CMI decision procedure as an oracle, it becomes possible to search the space of assignments and identify missing characteristic models. This result is significant because it suggests that the difficulty of these tasks is inherent to the relationship between the representations, rather than the direction of the translation.
Connections to Hypergraph Theory and Databases
The paper bridges AI representation with combinatorial optimization by relating these translations to the Hypergraph Transversal Problem (HTR). HTR involves finding minimal sets of nodes that intersect every edge in a hypergraph. The author proves that the translation problems are HTR-Hard.
HTR occupies a unique position in complexity theory; it is known to have a sub-exponential algorithm ($n^{O(\log n)}$), suggesting it is likely not NP-Complete, yet no standard polynomial-time algorithm has been discovered. By establishing this link, the paper places the AI translation tasks into this same "mysterious" complexity class.
Furthermore, the paper identifies a mathematical duality in database theory. The process of translating between Horn expressions and characteristic models is functionally identical to translating between Functional Dependencies and Armstrong Relations in relational databases. This cross-disciplinary connection allows researchers to apply insights from database design to AI knowledge representation.
Complexity Landscape and Limitations
The research provides a clear hierarchy of complexity for these tasks:
- CCM ≡ SID ≡ CMI: These core problems are equivalent and HTR-Hard.
- Entailment of Closure (EOC): The problem of deciding if a formula is implied by the intersection-closure of an arbitrary set of assignments is proven to be co-NP-Complete. This underscores that the specific structure of characteristic models is what prevents the translation from becoming even more computationally difficult.
One major caveat identified is the "exponential gap." Even if efficient algorithms are found, the size of one representation can be exponentially larger than the other for certain knowledge bases. This means that for some domains, a compact Horn formula might result in a massive set of characteristic models, or vice versa, making translation impractical regardless of algorithmic efficiency.
Conclusion
This paper provides a rigorous foundation for understanding the costs of switching between formula-based and model-based Horn representations. By proving the equivalence of the translation tasks and linking them to the hypergraph transversal problem, the work clarifies the computational boundaries of knowledge representation. While the exact complexity of HTR remains an open question, this research ensures that any progress in that classic problem will immediately translate to more efficient AI reasoning systems.
Summary updated