Efficient Reasoning
- Russ Greiner, Dept of Computing Science; PI of AICML
- Christian Darken
- N. Iwan Santoso
Many tasks require 'reasoning' --- ie, deriving conclusions from a corpus of explicitly stored information --- to solve their range of problems. An ideal reasoning system would produce all-and-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.
Citation
R. Greiner, C. Darken, N. Iwan Santoso. "Efficient Reasoning". Computing Surveys, 33(1), pp 1--30, March 2001.| Keywords: | efficient, Reasoning |
| Category: | In Journal |
BibTeX
@article{Greiner+al:ComputingSurveys01,
author = {Russ Greiner and Christian Darken and N. Iwan Santoso},
title = {Efficient Reasoning},
Volume = "33",
Number = "1",
Pages = {1--30},
journal = {Computing Surveys},
year = 2001,
}Last Updated: April 25, 2007Submitted by Russ Greiner
