Artificial Intelligence Seminar
Winter 1996
Wednesdays 14:00 - 15:20, Deschutes 200
Tractable Approaches to Logical Deduction
Since logical deduction is NP-complete in the propositional case and
undecidable in general, building practical reasoning systems presents
difficult choices. In some cases, sound and complete methods may be
refined to the point where they are adequate for a particular class of
problems (this was a topic of James Crawford's AI seminar last winter).
In other cases, however, something must be given up in order to achieve
reasonable performance. The obvious candidates are expressive power,
soundness, and completeness. Each of these has been the topic of
extensive investigation in the quest to build practical reasoners.
We will cover a variety of approaches to tractable knowledge
representation and reasoning, ranging through languages with restricted
expressive power, "knowledge compilation", multi-valued reasoning and
other incomplete techniques, and approximation.
We will likely begin with Lipski's early work on approximate answers
to database queries, which foreshadows some of the key ideas that have
recently attracted interest, consider logics of relevance and explicit
belief from the 1980's, and end with compilation, approximation, and
hierarchical schemes.
The
class schedule and
reading list are now available.
Back to David Etherington's
home page.