Abstract
This paper establishes a critical bridge between nonmonotonic reasoning—specifically Reiter’s Default Logic—and the well-studied domains of Propositional Logic and Constraint Satisfaction Problems (CSPs). By developing a polynomial-time mapping that transforms specific default theories into propositional sentences, the authors demonstrate how graph-based topological analysis can identify and solve tractable subsets of logic that were previously considered computationally intractable.
Introduction
In the early 1990s, Reiter’s Default Logic was a cornerstone of AI research for its ability to handle "common sense" reasoning (e.g., "Birds usually fly, but penguins are exceptions"). However, the logic faced a major hurdle: it is computationally devastating. Even simplified versions of the language often remain NP-hard or worse, making them impractical for real-world knowledge bases.
While most researchers at the time focused on restricting the syntax of the language to find "easy" versions, this paper takes a different route. Instead of just looking at the syntax, the authors examine the topology—the underlying structure of how rules and facts interact. They aim to find a way to use efficient algorithms from the field of Constraint Satisfaction to solve default logic problems.
Methodology
The authors introduce a three-step approach to tame default logic:
- Propositional Mapping: They define a transformation for a specific class of default theories called PDSD (Propositional Disjunction-free Semi-normal Default theories), mapping them into standard propositional logic sentences.
- Handling Circularity: A major challenge in default logic is avoiding "unfounded" or circular proofs. To solve this in the cyclic case, the authors introduce index variables. These variables enforce a partial ordering, ensuring that every belief in an "extension" (a consistent set of beliefs) has a grounded, non-circular justification.
- Constraint Network Translation: Once the theory is in propositional form, it can be viewed as a constraint network. The authors apply Tree-Clustering—a technique that decomposes a complex graph of constraints into a tree of "cliques." If the "induced width" ($w^*$) of this graph is small, the problem becomes much easier to solve.
Key Insights: Logic as a Graph
The most significant insight is that the difficulty of reasoning isn't just about the number of rules, but how they are connected. By treating a knowledge base as a graph, we can use topological parameters like induced width and cycle-cutsets to predict exactly how hard a problem will be before we even try to solve it.
The paper proves that every "model" of their translated propositional theory corresponds exactly to an "extension" of the original default theory. This effectively turns a nonmonotonic reasoning task into a standard Satisfiability (SAT) problem. Furthermore, by using the Tree-Clustering method, the authors show that you can perform an expensive one-time preprocessing step. Once the "tree" is built, you can answer queries about the knowledge base in linear time, which is ideal for systems that need to handle many incoming questions quickly.
Key Results
- Polynomial Translation: The authors show that any PDSD can be translated into propositional logic in polynomial time and space ($O(|W| + |D|n^3)$).
- Complexity Bounds: They establish concrete complexity bounds based on the graph's structure. For an acyclic theory with an induced width $w^*$, tasks like finding an extension can be decided in $O(n \cdot 2^{w^*+1})$ steps.
- Tractability Identification: The mapping allows them to identify new tractable classes. For example, they show that "Prerequisite-free normal unary" theories map to 2-SAT, which can be solved in linear time.
Limitations and Future Work
The current mapping is limited to PDSDs (disjunction-free and semi-normal). While this covers many common use cases, it doesn't yet handle the full expressive power of Reiter’s original logic. Additionally, the efficiency of the Tree-Clustering method depends heavily on the induced width ($w^*$). If the knowledge base is highly interconnected (a "dense" graph), the $w^*$ will be high, and the preprocessing step will remain exponentially expensive. Future directions include extending this framework to "network default theories" and general disjunctive theories.
Summary updated