The Complexity of Belief Update

1 Introduction

The study of belief change has received considerable at­ tention from the AI, databases and philosophy commu­ nities. Belief change deals with the incorporation of new facts into an agent's beliefs. There are two basic forms of belief change: belief revision and belief update. The difference lies in what is the source of incorrectness (if any) in the previous agent's beliefs.

The old beliefs of the agent may be mistaken or in­ complete: in this case the usual approach is that of belief revision, captured by the AGM postulates [Alchourr6n et al., 1985). On the other hand, an agent's beliefs, while correct at one time, may become obsolete due to changes in the world. The basic treatment of updates is given in [Winslett, 1990), while a general framework is proposed in [Katsuno and Mendelzon, 1991).

Many drawbacks and limitations of the initial proposal of Winslett have been discovered. One regards how it treats disjunctive information: as in many approaches of non-monotonic reasoning, the update treats incorrectly a new piece of information that is in disjunctive form (such as x1 V x2 ). The next example shows one of these situations.

Example 1 The RCH company deals with computers. It stores computers not yet sold in a warehouse composed by three separated rooms. The first room contains PCs, the second Macintoshes and the third Suns, X-terminals etc. By accident, a fire is set up in the room that con­ tains PCs, and all the items it contains are moved to the other two rooms. The old database is (for our pur­ poses) --.contains(PC, R2)/\--.contains(PC, R3), which means only the first room contains PCs. After the fire destroyed that room, all we know is that the PCs has been moved in the rooms R2 and R3. Some items may have been moved to a room and some to the other one. The new piece of information to be incorporated is 1-l = contains(PC, R2) V contains( PC, R3), which denotes the fact that at least one room (possibly both) must have PCs in it. The intended result of the update should be 1-l itself, but Winslett's gives instead contains(PC, R2) =I contains(PC, R3). This is not the intuitive result, since the possibility that some items have gone to R2 and some to R3 should not be ruled out.

Another drawback of the original formulation of up­ date is that it never allows changes to the previous states: sometimes updates lead agents to revise their knowledge about the previous state. In these cases, update is re­ lated with revision as intended in the AGM framework [Alchourr6n et al., 1985; Dalal, 1988). The next exam­ ple, shamelessly stolen from [Boutilier, 1995), shows this fact.

Example 2 We have a beaker with an unknown liquid in it. We want to determine if it is an acid or a base. Initially, all we know is acid =I base: the content of the beaker may be an acid or a base, but not both.

In order to determine which kind of substance we are dealing with, we drop a litmus paper in the beaker. After that, we discover that the liquid is an acid. Updating the old knowledge base we obtain (correctly) acid 1\ --.base. The problem is that this fact is true not only after the experiment, but was also true before it: the liquid was acid before the test, although we did not know this. As a result, the initial state should be modified accord­ ingly. However, Winslett's approach modifies only the new state, and does not make any change on the belief about the previous state: using this update, we can say, about the liquid before the test, only acid =I base.

In this paper we analyze the complexity of some of the proposals introduced so far. The complexity of the PMA approach (Possible Models Approach, also known as Winslett's update) has been proved by Eiter and Got­ tlob [1992] to be at the second level of the polynomial hierarchy, namely II~. The problem considered there is the basic entailment, that is given a knowledge base ¢, an update f..L and a propositional formula ¢, decide whether 'ljJ is implied by ¢*w f..L, the updated knowledge base The paper is organized as follows: in the next section we give the basic definitions of propositional calculus, belief update, and the various definitions of update pro­ posed so far. In section 3 we study the updates proposed for solving the problem of disjunctive updates: we start showing how some of the semantics of update are related to previous work on closed world reasoning, and use the results on complexity of closed world reasoning to prove some complexity results of update. In section 4 we show the complexity of the remaining proposals. In section 5 we draw some conclusions.

2 Definitions

Throughout this paper, we assume a propositional lan­ guage £ over an alphabet of atoms X. Any piece of information (such as previous agents' beliefs, updates, etc.) is represented by a propositional formula, where not otherwise specified. An interpretation is a truth as­ signment of the atoms, that is, a function from atoms into the set {true, false} . We extend this assignment to propositional formulas in the usual way. An inter­ pretation I is a model of a formula ¢ if and only if the formula is true in that interpretation. We denote inter­ pretations and models by sets of atoms (those mapped into true). The set of all the possible interpretations over the given alphabet is denoted by M. A formula is said to be complete if it has exactly one model. Given a formula ¢, we denote by Var(¢) the set of atoms it contains.

We denote by Mod(¢) the set of all the models of the formula ¢. We use also Form to denote the inverse func­ tion of Mod, that is, Form(A) is a propositional formula whose set of models is A. This function is not unique, since equivalent formulas have the same set of models; however, this is unimportant for our purposes.

Given two interpretations I and J, we denote by Diff(I, J) their symmetric difference, that is, Diff(I, J) = I\J U J\f. Intuitively, Diff(I, J) is the set of atoms to which the interpretations I and J assign a different truth value. Given a set A and an ordering<, we denote by min(A, <) the set of the minimal elements of A w.r.t. the ordering <.

We sometimes use substitutions. A substitution is a set of pairs atom/ formula. Given a substitution S = {x;j¢;}, and a propositional formula J.L, we denote by J.L[ S] the formula obtained from f..L by replacing any occurrence of Xi with the corresponding '1/Ji·

2.1 Winslett's Update

Consider a propositional formula¢ representing the state of the world. This information is assumed to be correct, but not (necessarily) complete. When a change in the world occurs, this description of the world must be mod­ ified. The assumption behind belief update is that what we know about the change is a propositional formula f..L that is true in the new situation.

Winslett's update operates on a model by model base. Let I be an interpretation, and define '5.1 to be the or­ dering on interpretations defined as

The update of the old state ¢ when a new formula f..L becomes true after a change is

This update was initially proposed in the context of databases, in which one can safely assume that all the updates are atomic, that is, the formula f..L is always a literal. In AI this is often considered to be too restrictive. When f..L is allowed to be any formula, and mainly when it is a disjunction of literals, the result of the Winslett's update may be intuitively incorrect. The example 1 of the last section shows a situation of this kind.

2.2 Minimal Change with Exceptions

This approach, introduced in [Zhang and Foo, 1996], at­ tempts to overcome the non-intuitive treatment of dis­ junctive information of the original formulation. The definition is similar to that of Winslett's update, except for a set of atoms EXC that are not considered in the computation of the symmetric difference between inter­ pretations.

First, define D(J.L) as the set of all the minimal clauses implied by J.L , that is

Then define EXC(I, J.L), where I is an interpretation and f..L a formula, as

Then, define '5.f, where R is a set of variables, as the ordering among interpretations such that

finally, the update is defined as

2.3 Minimal Change with Maximal Disjunctive Inclusion

Given a model I and a set of models S, define [Zhang and Foo, 1996]

then define the result of the update as

This approach is different from the previous one. Let ¢>and J.L be as follows.

The initial knowledge base ¢> has only one model I = 0 (the interpretation that assigns false to all the variables). The only element of D(p,) that has not I has a model is x1 V x2. As a result, EXC(I,p,) = {x1,x2} and thus ¢> *MCE J.L = (x1 =P x2) 1\ -.x3 1\ -.x4.

On the other hand, ¢> *MCD J.L = J.L 1\ -.x4. Indeed, min(Mod(p,), ::;I) = { { xl}, { x2}}, that has three subsets. The first is {xl}: we have Dis(I,{{xl}}) = {{xl}}. The second is {x2}, for which Dis(I, {{x2}}) = { {x2}}. The last subset is {{ xl}, { x2}} itself. One can verify that Dis(I,{{xl},{x2}}) = {{x1,x2,x3}}. Thus, the models of the updated knowledge base are {xl}, {x2}, and { x1, x2, x3}. The formula J.L 1\ -.x4 represents this set of models.

2.4 Update with Dependence Function

Assume that there is a function DEP from atoms to set of atoms. We use DEP(xi) to denote the set of atoms whose value depends on that of Xi· This means that a change in the value of Xi may affect the value of a Xj E DEP(xi) (see [Herzig, 1996], where the operator is introduced, for more details.) It is assumed that for any atom Xi, it holds Xi E DEP(xi). Define DEP(p,) as the union of DEP(xi) for each Xi E Var(p,).

Now, define

and the update is defined as

2.5 Generalized Update

This operator was introduced in [Boutilier, 1995] to for­ malize scenarios where an update may lead to revising the knowledge about the initial state. Define a rank­ ing "' as a partial function from interpretations to in­ tegers, such that there is at least one interpretation I

such that "'(I) = 0. The meaning of this ranking is that if "'(I) < "'( J) then the interpretation I is believed to be more plausible than J, the world described exactly by I is more likely than the world described by J, from the agent's perspective. The models of¢> must be exactly those ranked 0. When "'(I) is not defined, the model I is considered unplausible. In this case, we write "'(I) = oo.

We formalize the possible changes in the world as a set of possible events that may occur. For each event, we must specify what is the plausibility that the possible world represented by a model I will be transformed into the world represented by another model J. This plausi­ bility is a function e from triples (event,model,model) to integers. It can be a partial function, and e(e, I, J) = oo means that in the event e, the transition from I to J is considered implausible.

A generalized update model is a 5-tuple (M, "'' e, E, m), where M is as usual the set of all the interpretations, "' is a ranking, E is a set of events, e is as said above a function from triples (event,model,model) to integers, and m is a function from pairs (event,model) to integers, representing the plausibility of the occur­ rence of an event in the world represented by a given model.

Define the new rank of the interpretations after the update as

This function J<i, 0 (J) induces an ordering in a natural way: I ::;o J if and only if J<i, 0 (I) ::::; "' 0 (J). One way to define the update is

that is, the models of the result are the models of J.L whose rank "'o is minimal.

2.6 Possible Causes Approach

This approach was proposed in [Li and Pereira, 1996] and is based upon the idea that changes in the world are caused by actions. Thus, update can be formalized with ad-hoc languages such as A (introduced in [Gelfond and Lifschitz, 1993]) with an appropriate semantics. The main difference between reasoning about actions and be­ lief update formalisms is that in the formers, actions are often assumed to be known in advance, and the aim of the theory is to understand what is true after they are performed. In belief update, actions are always assumed unknown, and the only evidence they have happened is their consequences.

The language A is built over an alphabet composed of fluent names (that are the facts, or what in the pre­ vious formalizations are the atoms of the propositional language), and three special symbols after, causes and if. A fluent expression is a fluent name or a fluent name preceded by --. . Propositions are of two types: value propositions F after A1; ... ; Am, where F is a fluent expression and A1; ... ; Am are actions; and ef­ fect propositions A causes F if P1, . .. , Pm, where A

is an action and F, P1 , ..· , Pm are fluent expressions. If m = 0 the after proposition F after A1 , ... , Am is writ­ ten initially F, and is called initially proposition.

In order to formalize the belief update in this frame­ work, we must introduce a finite set of (linearly or­ dered) temporal points T, and two other kinds of propo­ sitions, the happens propositions and the holds proposi­ tions. Given a time point t and an action A, a happens proposition is w.ritten A happens at t, and means that the action A happens in the instant t. Given a fluent expression F and a time point t, a holds proposition has the form F holds at t, and means that F is true in the time point t.

A domain description is a set of value, effect, and hap­ pens propositions. Given a domain description D, it may happen that new information, represented by a holds proposition H, has to be incorporated. Due to the lack of space, we cannot introduce formally the semantics of A neither that of the belief update based on it. We refer to [Li and Pereira, 1996], where the update is introduced, for a more detailed explanation. The new holds proposi­ tion H could be not implied by D. In this case, we must find an explanation, i.e., a possible cause of the change. Formally, an explanation is a set of happens and initially propositions P such that D UP implies H. To decide whether a proposition H' is implied by the updated de­ scription, we check whether D U P implies H' for each minimal explanation P.

2. 7 Closed World Reasoning

In the sequel we use two formalizations of the closed world assumption, namely the generalized world closed assumption and the CURB.

Given a propositional formula J.L, the set of its free for negation atoms, written F F N (J.L), is the set of the atoms that are false in all the minimal (w.r.t. set inclusion) models of J.L. The generalized closed world assumption of J.L is the formula GCWA(J.L) = J.L I\ F F N(J.L).

The CURB is introduced in [Eiter et al., 1993] as a variant of the circumscription-. In this paper we use a simplified version of it, the CURB 1 , also introduced in the paper above. Given a formula J.L, the CURB 1 (J.L) is defined as the formula whose models are the models J of J.L such that there exists a set of minimal models S of J.L such that a) J contains all the models of S, and b) there is no other J' of J.L, contained in J, with the same property.

2.8 Computational Complexity

We assume that the reader is familiar with the basic concepts of computational complexity. We use the stan­ dard notation of complexity classes that can be found in [Johnson, 1990]. Namely, the class P denotes the set of problems whose solution can be found in polynomial time by a deterministic Thring machine, while NP de­ notes the class of problems that can be resolved in poly­ nomial time by a non-deterministic Thring machine. The class coNP denotes the set of decision problems whose complement is in NP. We call NP-hard a problem G if any instance of a generic problem NP can can reduced to an instance of G by means of a polynomial-time (many­ one) transformation (the same for coNP hard).

Clearly, P ~ NP and P ~ coNP. We assume, following the mainstream of computational complexity, that these containments are strict, that is P ::/: NP and P ::/: coNP.

We also use higher complexity classes defined using or­ acles. In particular pA (NPA) corresponds to the class of decision problems that are solved in polynomial time by deterministic (nondeterministic) Thring machines us­ ing an oracle for A in polynomial time (for a much more detailed presentation we refer the reader to [Johnson, 1990]). The classes ~~, II~ and ~~ of the polynomial hierarchy are defined by ~0 = IIg = ~g = P, and for k ~ 0,

3 Disjunctive Information

In this section we analyze the definitions proposed to manage the problem of disjunctive information in belief update. The reason of their introduction is that updat­ ing -,x I\ -,y with x V y one does not want, in general, to obtain x ::/: y, that is the result given by Winslett's update.

This problem is analogous of that of other forms of non monotonic reasoning, notably circumscription and closed-word reasoning.

We start with the two proposals by Zhang and Foo. The minimal change with exception update have some similarities with the generalized closed world assump­ tion. Indeed, GCWA can be reduced to MCE, and vice versa.

Theorem 1 For any propositional formulas¢ and J.L, it holds

where X is the set of atoms of J.L and S is the substitution {xi/-,xilxi E I}.

This proves that *MCE is based upon the concept of generalized closed world assumption. As a result of the first statement, the update *MCE is II~ hard, since the generalized closed world assumption is so, [Eiter and Gottlob, 1993], and it can be reduced polynomially to *MCE· About the membership in that class, we note that the second statement gives a non-polynomial re­ duction. The following theorem shows the complexity of *MCE·

Theorem 2 The update *MCE is II~ complete.

This can actually proved in a very simple manner using the result of II~ membership of GCWA given by Nebel [1996].

While the minimal change with exception is based upon the generalized closed world assumption, the mini­ mal change with maximal disjunctive inclusion update is similar to the variant of circumscription called CURB 1 . About the relation between* MCD and CURB 1 , we have the following theorem.

Theorem 3 For any propositional formulas ¢> and f.L, it holds

where S is the substitution { xd -.x; lx; E I} .

This theorem shows also that the *MCD is 11~ hard, since this is the complexity of CURB 1 , as proved in [Eiter et al., 1993].

The second reduction is not polynomial. However, with a little effort it is possible to obtain the exact com­ plexity of *MCD·

Theorem 4 The update *MCD is 11~ complete.

The update with dependence function is based on a function DEP that represents the causal relations be­ tween literals of the given alphabet. The easiest case is having all literals independent from each other, that is DEP(x;) =={xi}. In this case, the following theorem shows that the Herzig's proposal coincides with the stan­ dard semantics update *ssu (for an explanation of the standard semantics update see [Winslett, 1990]).

Theorem 5 When DEP is defined as DEP(x;) ={xi} for each x;, then for each pair of propositional formulas ¢> and f.l it holds ¢>*He f.l = ¢> *ssu f.l·

A more general statement can be given. Recall that a way to represent the logical consequences of¢ *ssu f.l is ¢>[{xi/z;lx; E Var(JL)}]I\f.l, where z; are new variables appearing nowhere else. For *He we have the following lemma.

Lemma 1 For each triple of propositional formulas ¢>, f.l and 1/J, it holds ¢>*He f.l f= 1/J if and only if¢>[ { x;/ zdx; E DEP(JL)}]I\ f.L f= 1/J, where z; 's are variables that do not appear in any of the three formulas .

Assuming that verifying whether x; E DEP(JL) is a polynomial task, we have the following result.

Theorem 6 The update with dependence function is coNP complete.

4 Complexity of Generalized Updates

In this section, we show the complexity of the two other updates, the generalized update by Boutilier [1995] and the possible causes approach by Li and Pereira [1996]. The former turns out to be simpler than the basic (Winslett's) update, while the latter is one level higher in the polynomial hierarchy.

About Boutilier's generalized update, we have to make some computational assumptions on the functions in­ volved. Namely, we still write ¢>*au f.L, and we implicitly assume that E is part of the input, but not M (this is the set of all the interpretations over the given alpha­ bet). Also, we assume that the functions K, e and m of the revision model can be calculated in polynomial time. This means that given an event e and two models I and J, it must be possible to determine the .integer e(e, I, J) in polynomial time. The same for "' and m.

Under these assumptions, the entailment problem for this update is a D.~ problem.

Theorem 7 The update *au is D.~.

We give a very short explanation of this result . As for Dalal's revision, the check ¢>*au f.L f= 1/J can be done in two steps: first, determine the value of the minimum K(I) + e(e, I , J) + m(e, I). Using this value kq, ,p., verify­ ing whether ¢> *au f.L f= 1/J is a coNP complete problem. Indeed, guess a model I of¢, a model J of f.l and an event e such that K(I) + e(e, I, J) + m(e, I) = kq, ,p. and J fl. Mod( 1/J). If this is possible, then ¢> *au f.l ~ 1/J.

The first step, the determination of kq, ,p. , can be done with a polynomial number of calls to an NP or­ acle. Start with a guess for kq,,p., and verify (with the oracle) whether there exist I, J and e such that K(I) + e(e, I, J) + m(e, I) is less than this number. If this is true, the value of this kq, ,p. must be decreased (otherwise, it must be increased).

About the hardness of this update, we note that one of the revision introduced, namely Dalal's revision [Dalal, 1988], can be polynomially reduced to the generalized update.

Theorem 8 Let e be the function such that e( e, I, J) is the number of elements in Diff (I, J). Then, using the revision models (M, K, e, { e }, m) where k(I) = 0 if IE model(¢>) and K(I) = oo otherwise, and m(e, I) = 0, then¢> *GU f.l = ¢> *D f.L, where *D is the Dalal 's revision.

As a corollary, since the revision of Dalal is D.~(logn] complete, the complexity of the generalized update is D.~(logn] hard. This result can be strengthened.

Theorem 9 The generalized update is D.~ complete.

The Generalized Update has a lower complexity than Winslett's update. Thus (unless the polynomial hierar­ chy collapses) it is impossible to reduce the latter to the former in polynomial time.

We now consider the Possible Causes Approach. The problem we analyze is still to decide whether a formula is entailed by the old knowledge (in this case, a domain description) updated with a holds proposition.

Theorem 10 Entailment under the Possible Causes Approach is 11~ complete.

This is the only update considered in this work that turns out to be more complex than Winslett's. We try to explain this result .

Consider the definition of the possible causes approach restricted with the following hypothesis.

1. There are no holds proposition in the domain de­ scription (the only holds proposition is the update).
2. Given the set of fluents {P1 , . .. , Pn}, there are only n actions {A1 , ... , An}, and the only effect propo­ sitions in the domain description are

1. Explanations are composed only of after proposi­ tions (initially propositions are not allowed in ex­ planations) .

In the holds propositions P holds at t we allow P to be a boolean formula on the alphabet of the fluent names (instead of a fluent expression). Under these restrictions, the update is still IT~ complete.

The reason of the increase of the complexity is that, in the Winslett's approach, each model of¢ is updated separately, and this makes easy to verify if the result of an action entails the new piece of information.

Given a model I E Mod(¢), in order to decide if J E min(Mod(J.L), S:I ), we have to check whether Diff(I, J) is minimal. Each element of Diff(I, J) can be interpreted as an action of the kind of (b) above, that changes the value of a literal. As a result, an explanation of the change is a minimal set of actions that maps I into a model of J.L. Given a model I and a set of those ac­ tions, deciding whether the resulting interpretation J is a model of J.L is a polynomial problem.

In the PCA, the possible causes affect the initial state D altogether: a possible explanation is a set of propo­ sitions P such that D U P implies the new fact to be incorporated. This is more complex than verifying a possible explanation in Winslett's approach.

5 Conclusions

In this paper we have investigated some of the seman­ tics that have been introduced to formalize changes in the world of interest. The complexity of most of them turns out to be at the second level of the polynomial hi­ erarchy. This is quite a remarkable result: indeed, these frameworks have been proposed to overcome drawbacks and limitations of the original semantics of update intro­ duced by Winslett, but this does not seem to introduce any increase in the computational complexity.

Two approaches turn out to have a different complex­ ity than Winslett's. The first is Boutilier's Generalized Update, that is easier (D.~ complete), and the second is the Possible Causes Approach by Li and Pereira, that is more difficult (IT~ complete). The first one is a gen­ eralization of Dalal's revision, and has a slightly higher complexity. The reason of the higher complexity of the Possible Causes Approach seems to be the globality of this operator: a change is considered not to affect each single possible initial state, but all the possible initial states altogether. This makes NP complete a subprob­ lem that is polynomial in Winslett's approach.

Acknowledgments

We would like to thank Marco Schaer£ for revising a draft version of this paper. Most of the work reported here has been done while the author was visiting AT&T Bell Labs. We thank Henry Kautz for his support during this period.