Tractable abduction

Abduction can be described as “inference to the best explanation,” which includes the generation, criticism, and possible acceptance of explanatory hypotheses. What makes one explanatory hypothesis better than another are such considerations as explanatory power, plausibility, parsimony, and internal consistency. In general a hypothesis should be accepted only if it surpasses other explanations for the same data by a distinct margin and only if a thorough search was conducted for other plausible explanations.

Abduction seems to be an especially appropriate and insightful way to describe the evidence-combining characteristics of a variety of cognitive and perceptual processes, such as diagnosis, scientific theory formation, comprehension of written and spoken language, visual object recognition, and inferring intentions from behavior. Thus abductive inference appears to be ubiquitous in cognition. Moreover, humans can often interpret images, understand sentences, form causal theories of everyday events, and so on, apparently making complex abductive inferences in fractions of a second.

Yet the abstract task of inferring the best explanation for a given set of data, as the task was characterized in chapter 7, has been proved to be computationally intractable under ordinary circumstances. Clearly there is a basic tension among the intractability of the abduction task, the ubiquity of abductive processes, and the rapidity with which humans seem to make abductive inferences. An adequate model of abduction must explain how cognitive agents can make complex abductive inferences routinely and rapidly.