Efficient reasoning

Publisher Website
Google Scholar
Abstract
Many tasks require “reasoning”—i.e., deriving conclusions from a corpus of explicitly stored information—to solve their range of problems. An ideal reasoning system would produce all-and-only thecorrectanswers to every possible query, produce answers that are asspecificas possible, beexpressiveenough to permit any possible fact to be stored and any possible query to be asked, and be (time)efficient. Unfortunately, this is provably impossible: 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-based reasoning, then overviews the techniques now used to address, or at least side-step, this dilemma.