On the complexity of propositional knowledge base revision, updates, and counterfactuals

Abstract

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 T ○ p, 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.