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.
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