Translating between Horn Representations and their Characteristic Models

Roni Khardon

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:

  1. Computing Characteristic Models (CCM): Given a Horn formula, find its set of characteristic models.
  2. Structure Identification (SID): Given a set of models, find the underlying Horn formula that represents them.
  3. 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

Abstract

Characteristic models are an alternative, model based, representation for Horn expressions. It has been shown that these two representations are incomparable and each has its advantages over the other. It is therefore natural to ask what is the cost of translating, back and forth, between these representations. Interestingly, the same translation questions arise in database theory, where it has applications to the design of relational databases. This paper studies the computational complexity of these problems. Our main result is that the two translation problems are equivalent under polynomial reductions, and that they are equivalent to the corresponding decision problem. Namely, translating is equivalent to deciding whether a given set of models is the set of characteristic models for a given Horn expression. We also relate these problems to the hypergraph transversal problem, a well known problem which is related to other applications in AI and for which no polynomial time algorithm is known. It is shown that in general our translation problems are at least as hard as the hypergraph transversal problem, and in a special case they are equivalent to it.
BibTeX
@article{khardon1995translating,
  author = {Roni Khardon},
  title = {{Translating between Horn Representations and their Characteristic Models}},
  journal = {J. Artif. Intell. Res.},
  year = {1995},
  url = {https://openreview.net/forum?id=M_5veFAaYuq},
}
Figure