### Efficient reasoningEfficient reasoning

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

Source: ACM Digital Library