Translating between Horn Representations and their Characteristic Models

Roni Khardon

TL;DR

This paper explores the computational complexity of moving between two ways of representing knowledge: logical Horn formulas and their "characteristic models." The author proves that translating in either direction is equally difficult and establishes a deep connection to the famous Hypergraph Transversal Problem, placing these AI tasks into a well-defined but still mysterious complexity class.

What Problem Does This Paper Address?

In Artificial Intelligence, we often represent knowledge using logical formulas. Horn formulas (rules like "if A and B, then C") are particularly popular because they allow for very fast deduction. However, for other tasks like abduction (finding the best explanation for an observation) or default reasoning, using formulas is computationally expensive (NP-Hard).

An alternative is to represent knowledge using a specific subset of examples, known as characteristic models. While formulas are great for some tasks, these models are better for others. Naturally, researchers want to "have their cake and eat it too" by translating between the two representations.

The paper addresses three specific questions:

  1. CCM (Computing Characteristic Models): Can we efficiently find the models given a formula?
  2. SID (Structure Identification): Can we find the underlying Horn formula given a set of models?
  3. CMI (Characteristic Models Identification): Can we at least decide if a given set of models correctly represents a specific formula?

Methods

The author employs computational complexity theory, specifically using polynomial reductions to show how these problems relate to one another.

A key technique used in the proofs is the "substitution trick." To find a counter-example (a model that should be in the set but isn't), the author shows how to systematically fix variables to "1" or "0" and use a decision procedure (CMI) as an oracle to narrow down the search.

The paper also draws heavily on Monotone Theory. By viewing Boolean functions through the lens of partial orders (lattices), the author bridges the gap between logical Horn expressions and the combinatorial structure of hypergraphs. This allows for a comparison with the Hypergraph Transversal Problem (HTR)—a classic problem of finding minimal sets of nodes that "touch" every edge in a hypergraph.

Datasets

As a theoretical computer science paper, no empirical datasets or benchmarks were used. The "evaluation" consists of formal mathematical proofs and the construction of specific Boolean functions (like the Aizenstein & Pitt functions) to demonstrate exponential gaps between different representation sizes.

Key Insights and Ideas

  • The Equivalence of Translation and Decision: One of the most significant "aha" moments is that the search problems (CCM and SID) are exactly as hard as the decision problem (CMI). If you can check whether a set of models is correct in polynomial time, you can also generate that set in polynomial time (relative to the size of the output).
  • The HTR Connection: The paper establishes that these AI translation problems are at least as hard as the Hypergraph Transversal Problem. HTR is a "famous" problem because it occupies a strange middle ground: it has a sub-exponential algorithm ($n^{O(\log n)}$), meaning it's likely not NP-Complete, but no one has found a standard polynomial-time algorithm for it yet.
  • Database Duality: The author points out a fascinating parallel in database theory. Translating between Horn expressions and models is mathematically equivalent to translating between Functional Dependencies and Armstrong Relations in relational databases. This means results in AI and database theory can be cross-pollinated.
  • The "Exponential Gap" Warning: The paper cautions that even if we have "relaxed" versions of these problems (like computing all prime implicants), they might still be inefficient because the number of prime implicants can be exponentially larger than the number of characteristic models.

Key Results

The paper provides a clear hierarchy of complexity (summarized in the paper's Figure 1):

  1. CCM $\equiv$ SID $\equiv$ CMI: These three core problems are computationally equivalent.
  2. Hardness: These problems are HTR-Hard. In a specific case where the Horn expression is represented by all its prime implicates, they are exactly equivalent to HTR.
  3. EOC is Harder: A slightly different problem, Entailment of Closure (EOC)—deciding if a formula is implied by the intersection-closure of a set of assignments—is proven to be co-NP-Complete. This highlights that the requirement for the input models to be "satisfying assignments" in CMI is a crucial constraint that keeps the problem from becoming even harder.

Limitations and Future Work

The primary limitation is that the exact complexity of HTR (and thus CCM/SID) remains an open question. While we know they are "easier" than NP-Complete problems due to the existence of sub-exponential algorithms, we still don't know if a true polynomial-time algorithm exists.

The author suggests that while characteristic models are powerful, the "exponential gap" in representation sizes means that for some knowledge bases, one representation will always be vastly more compact than the other. Future work could involve identifying specific subclasses of Horn formulas where these translations are guaranteed to be efficient (polynomial in the number of variables, not just the output size).

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},
}

Loading related content...

Figure