Thumbnail
Access Restriction
Subscribed

Author Greiner, Russell ♦ Darken, Christian ♦ Santoso, N. Iwan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Efficiency trade-offs ♦ Soundness/completeness/expressibility
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 the $\textit{correct}$ answers to every possible query, produce answers that are as $\textit{specific}$ as possible, be $\textit{expressive}$ enough to permit any possible fact to be stored and any possible query to be asked, and be (time) $\textit{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.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-03-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 33
Issue Number 1
Page Count 30
Starting Page 1
Ending Page 30


Open content in new tab

   Open content in new tab
Source: ACM Digital Library