Efficient reasoning

Many tasks require "reasoning"-i.e., deriving conclusions from a corpus of explicitly stored information-to solve their range of problems. An ideal re asoning system would produce all-and-only the correct answers to every poss ible query, produce answers that are as specific as possible, be expressive enough to permit any possible fact to be stored and any possible query to be asked, and be (time) efficient. Unfortunately, this is provably impossib le: as correct and precise systems become more expressive, they can become increasingly inefficient, or even undecidable. This survey first formalizes these hardness results, in the context of both logic- and probability-base d reasoning, then overviews the techniques now used to address, or at least side-step, this dilemma.