Teaching Sommersemester 2011

Seminar Knowledge Representation and Computational Tractability SS 2011

Submitted by vaishakbelle on 4. January 2011 - 18:11
Introduction

Knowledge Representation (KR) is a vibrant and exciting field in artificial intelligence. The endeavor rests on two fundamental ideas. First, to reason about the problem domain one must formalize it, perhaps in some logical formalism such as propositional logic or first-order logic. Second, for the representation to be useful one must be able to obtain reasonable and intuitive inferences in a timely fashion.
Unfortunately, propositional reasoning is intractable (Boolean reasoning is NP-COMPLETE) and first-order logic is undecidable. Thus, an important goal in the KR enterprise is to find a tradeoff be- tween the expressiveness of the representational language and the computational behavior of associated reasoning tasks. A main objective of this seminar is to discuss approaches bordering this tradeoff.