The complexity of belief update Original Research Article

Belief revision and belief update are two different forms of belief change, and they serve different purposes. In this paper we focus on belief update, the formalization of change in beliefs due to changes in the world. The complexity of the basic update (introduced by Winslett, 1990) has been determined by Eiter and Gottlob (1992). Since then, many other formalizations have been proposed to overcome the limitations and drawbacks of Winslettʹs update. In this paper we analyze the complexity of the proposals presented in the literature: the standard semantics by Winslett (1986), the minimal change with exception and the minimal change with maximal disjunctive information by Zhang and Foo (1996), the update with disjunctive function by Herzig (1996), the abduction-based update and the generalized update by Boutilier (1996). We relate some of these approaches to belief update to previous work on closed world reasoning.