**Topic:**

**GENERAL LOGIC**

## On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals

By Thomas Eiter and Georg Gottlob

We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases under the principle of minimal change. In particular, we derive complexity results for the following problem: given a knowledge base T, an update p, and a formula q, decide whether q is derivable from Tp, the updated (or revised) knowledge base. Note that this problem includes the evaluation of the counterfactual p > q over T, that is a conditional statement 'if p, then q' where p is known or expected to be false. We consider the general case where T is an arbitrary propositional formula (or theory) as well as restricted versions of this problem, in particular where T is a conjunction of Horn clauses, or where the size of the update p is bounded by a constant.

Download

Related post

Posted by Tony Marmo
at 00:01 GMT

Updated: Tuesday, 7 December 2004 23:02 GMT