Tractable default reasoning
Bart Selman · 1992
Commonsense knowledge is often incomplete, and reasoning with incomplete information is generally computationally intractable. For example, the statement John may come by train or by plane can force a system to reason by cases. We show how plausible default assumptions can be used to obtain more complete information (by filling in details), thereby providing a computational advantage in commonsense reasoning systems. Although it has been previously hypothesized that default reasoning might provide such an advantage, this is the first rigorous demonstration of the claim. A central aspect of this work is the analysis of the computational complexity of default reasoning. We characterize the various sources of intractability, and show how tractable forms of default reasoning can be obtained. Model-preference default theories are defined to provide a general default reasoning mechanism. We give a detailed analysis of the tradeoff between expressiveness and tractability as we place various syntactic restrictions on such theories. A similar analysis is given for Reiter's default logic, with an emphasis on efficiently computable default theories that include strict Horn theories. Our results indicate that the various tractable default theories are closely related. Our analysis of default logic also reveals the inherent intractability of abductive reasoning. Next, we consider the complexity of defeasible inheritance--a more specialized default reasoning formalism used in the representation of hierarchically organized information in semantic networks. Our central result is that inheritance reasoning based on Touretzky's inferential distance is NP-hard. Again, we identify the source of the intractability and delineate tractable subsystems. We conclude with a discussion of some of the computational limitations of the use of defaults in commonsense reasoning.