Bryan S Todd
Abstract:
In expert systems research, and more widely in computer science, a recurring and important problem is that of determining whether a boolean expression has a satisfying truth assignment. The general case is well known to be NP-complete, although efficient algorithms exist for many restricted classes. Unfortunately, the known feasible classes tend to be insufficiently expressive for knowledge representation. In this paper we transfer ideas from bayesian network theory to present a general-purpose algorithm for evaluating boolean expressions. The algorithm is a special case of that due to Lauritzen and Spiegelhater for propagating evidence through bayesian networks. The algorithm is efficient for a large class of boolean expressions of practical relevance and may possibly offer a useful alternative to other general-purpose tautology checkers.