Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Knowledge Representation and Logic

Several forms of reasoning in AI -- like abduction, closed world reasoning, circumscription, and disjunctive logic programming -- are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the powerful notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae (or of the disjunctive logic programs, resp.) is bounded by some constant. Experiments with a prototype implementation prove the feasibility of this new approach, in principle, and also give us hints for necessary improvements. In many areas of computer science, bounded treewidth has been shown to be a realistic and practically relevant restriction. We thus argue that bounded treewidth is a key factor in the development of efficient algorithms also in knowledge representation and reasoning -- despite the high worst case complexity of the problems of interest.