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 reasoning system would produce alland -only the correct answers to every possible 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 efficient. Unfortunately, this is provably impossible: as correct and precise systems become more expressive, they become increasingly inefficient, or even undecidable. This tutorial first formalizes these hardness results, in the context of both logic- and probability-based reasoning, then overviews the existing techniques now used to address, or at least side-step, this dilemma. Throughout, we also include some alternative proposals. 1 Introduction Many information systems use a corpus of explicitly stored information (a.k.a. a "knowledge base", KB) to solve their range of problems. For exa..