Abstract Computational efficiency is a central concern in the design of knowledge representation systems. Compiling a knowledgebase into a more tractable form has been suggested as a way around the inherent intractability of many representation formalisms. Because not all theories can be put into an equivalent tractable form, Selman and Kautz (1991) have suggested compiling a theory into upper and lower bounds (one logically weaker, the other logical stronger) that approximate the original information. A central question in this approach is how well the bounds capture the original knowledge. This question is inherently empirical. We present a detailed empirical evaluation of the compilation of two kinds of theories: computationally challenging randomly generated theories, and propositional encodings of planning problems. Our results show that one can answer a very high percentage of queries even using unit clause bounds, which are much easier to compute than more general tractable approximations. Furthermore, we demonstrate that many of the queries that can be answered by the bounds are expensive to answer using only the original theory: in other words, knowledge compilation does not just "skim off" easy queries. In fact, we show substantial total computational savings in using the bounds together with the original theory to answer all queries (with no errors) from a large benchmark set, over using the original theory alone. This study suggests that knowledge compilation may indeed be a practical approach for dealing with intractability in knowledge representation systems.
Introduction
In Knowledge Representation (KR), researchers face a fundamental trade-off between expressiveness and tractability. Systems capable of representing complex, real-world information using general logic often suffer from NP-hard query answering. Knowledge compilation offers a potential solution by pre-processing a "hard" theory into a more tractable form. Since an exact tractable equivalent is not always possible, theory approximation uses two bounds: a Greatest Lower Bound (GLB), which is logically stronger, and a Least Upper Bound (LUB), which is logically weaker.
This paper empirically evaluates whether these bounds effectively capture original knowledge or merely "skim off" easy queries that standard solvers would have handled quickly regardless.
The Approximation Framework
The authors evaluate a specific framework for theory approximation using unit clauses as the target language. Unit clauses (simple lists of true/false literals) are chosen for their extreme processing speed. The query algorithm, KC-Query, operates as follows:
- Check if the query is entailed by the LUB. If yes, return "yes."
- If not, check if the query is entailed by the GLB. If no, return "no."
- If both bounds fail, resort to a full, expensive theorem prover (a Davis-Putnam "tableau" implementation).
Theoretical analysis suggests that this approach can provide exponential savings over the original theory in certain cases.
Experimental Setup
The approach was tested on two distinct datasets:
- Hard Random 3CNF Theories: Formulas with 75 to 200 variables at a clause-to-variable ratio (~4.3) known to be computationally difficult for SAT solvers.
- Mapworld: A planning domain where a robot navigates a graph. To ensure complexity, "forbidden pairs" of nodes were added (e.g., the robot cannot visit both node f and node j), transforming a simple pathfinding task into an NP-complete problem.
Performance Results
The experiments revealed that unit bounds are surprisingly powerful. Even with their simplicity, they answered between 66% and 100% of random queries. Crucially, the bounds did not just solve "easy" queries; many queries answered in linear time by the bounds were those that caused the standard theorem prover to struggle significantly.
For the largest random theories (200 variables), the knowledge compilation approach reduced the total time to answer 1,000 queries by over two orders of magnitude compared to the standard prover alone.
In the Mapworld domain, the KC-Query approach also outperformed the original theory. For human-designed queries, the speedup was approximately 2.5x, while for random predicates, it reached nearly 2.4x. The time saved during the query phase often compensated for the significant "off-line" time required for initial compilation.
Conclusion
Knowledge compilation via theory approximation is a viable strategy for managing intractability. While the initial compilation cost is high—taking roughly an hour for 200-variable theories—the amortized efficiency makes it ideal for static knowledge bases subject to frequent querying. Future work remains to determine if more complex Horn approximations justify their higher computational cost and how these techniques scale to modern, large-scale industrial problems.
Summary updated