On Computing Minimal Models

Rachel Ben-Eliyahu, Rina DechterAAAI 1993

In automated reasoning, finding the "simplest" explanations for a set of logical constraints is a fundamental challenge. This paper, originally presented at AAAI-93 by Rachel Ben-Eliyahu and Rina Dechter, explores efficient algorithms for computing minimal models—assignments of truth values that satisfy all rules while minimizing the number of variables set to "true."

The Importance of Minimality

Minimal models are central to several domains in Artificial Intelligence:

  • Diagnosis: Identifying the smallest set of component failures that explains a system's observed behavior, following the principle of Occam's Razor.
  • Circumscription: A form of non-monotonic reasoning where we assume normality unless evidence suggests otherwise.
  • Logic Programming: Determining stable models for complex databases.

While finding any model can be difficult, finding a minimal one is generally NP-hard. Ben-Eliyahu and Dechter aim to identify "islands of tractability" where specific logical structures allow for efficient computation.

Strategy 1: Exploiting "Almost-Horn" Theories

Horn theories, where each clause contains at most one positive literal, are well-known for being solvable in linear time. The authors extend this tractability to theories that are "near-Horn."

They introduce the positive graph representation, where nodes represent positive literals and edges connect literals appearing together in a clause. By finding a Vertex Cover—a subset of variables that covers all non-Horn components—the algorithms MinSAT and VC-minSAT can reduce a complex theory into a manageable Horn structure. The complexity becomes a function of the distance to tractability (the size of the vertex cover) rather than the total number of variables.

Strategy 2: Acyclic Networks and Tree-Clustering

The second strategy treats propositional logic as a Constraint Satisfaction Problem (CSP). By compiling a general theory into a "join-tree" (an acyclic network of relations), the authors can leverage tree-based algorithms.

A join-tree representation used for decomposing logical theories into acyclic structures.

Two primary algorithms are proposed for these structures:

  • Algorithm min1: A top-down approach that generates a subset of minimal models in a backtrack-free manner.
  • Algorithm min2: A bottom-up approach that computes all minimal models by pruning non-minimal partial assignments as it traverses the tree.

For theories that can be compiled into a tree with a maximum relation arity $k$, the complexity is $O(n2^k)$. This makes the approach highly effective for "near-tree" structures with low arity.

Key Insights and Complexity

The paper provides several rigorous complexity results:

  • 2-CNF Efficiency: Finding an X-minimal model (minimal over a specific subset of variables) for a 2-CNF theory takes $O(|X|n)$ time.
  • Hardness of Cardinality: While minimal models can sometimes be found efficiently, finding the minimum cardinality model (the one with the absolute fewest "true" values) remains NP-complete even for simple positive 2-CNF theories.
  • Output-Polynomial Time: For acyclic theories, the authors demonstrate that finding a subset of minimal models can be done in time proportional to the number of models produced, ensuring the algorithm scales with the size of the output.

Conclusion

By bridging the gap between theoretical complexity and practical structure, Ben-Eliyahu and Dechter's work provides a roadmap for efficient automated reasoning. While "loopy" or dense theories still pose a challenge due to the overhead of tree-clustering, the identification of near-Horn and near-tree structures offers a powerful toolset for real-world applications in diagnosis and logic programming.

Summary updated

BibTeX
@inproceedings{beneliyahu1993computing,
  author = {Rachel Ben-Eliyahu and Rina Dechter},
  title = {{On Computing Minimal Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure