Vivid Knowledge and Tractable Reasoning

Abstract

Mundane, everyday, reasoning is fast. Given the inherent complexity of sound and complete reasoning with representations expressive enough to capture what people seem to know, commonsense reasoning must require shortcuts and assumptions. Some means of simplifying the retrieval of the inferential consequences of a set of facts is obviously required. Instead of looking, as others have, at limited inference or syntactic restrictions on the representation, we explore the use of "vivid" forms for knowledge, in which determining the truth of a sentence is on the order of a database retrieval. In order to base a reasoning system on vivid knowledge, we consider ways to construct a vivid KB-a complete database of ground, atomic facts-given facts that may be presented in a more expressive language that allows incompleteness (e.g., first-order logic). Besides offering an architecture for examining these problems, our results show that some forms of incomplete knowledge can still be handled efficiently if we extend a vivid KB in a natural way. Most interesting is the way that this approach trades accuracy for speed.