THE COMPLEXITY OF NESTED COUNTERFACTUALS AND ITERATED KNOWLEDGE-BASE REVISIONS

We consider the computational complexity of evaluating nested counterf actuals over a propositional knowledge base. A counterfactual p > q is a conditional query with the meaning ''If p would be true in the know ledge base, would it then hold that also q is true,'' which is differe nt from material implication p double right arrow q. A nested counterf actual is a counterfactual statement where the premise p or the conclu sion q is a counterfactual. Statements of the form p(1) > (p(2) ... (p (n) > q) ...) intuitively correspond to conditional queries involving a sequence of revisions. We show that evaluating such statements is Pi (2)(P)- complete and that this task becomes PSPACE-complete if negatio n is allowed in a nesting of this form. We also consider nesting a cou nterfactual in the premise, i.e., (p > q) > r, and show that evaluatin g such statements is Pi(4)(P)-complete, thus most likely much harder t han evaluating p > (q > r). Finally, we also address iterated nestings in the premise and the mix of nestings in the premise and the conclus ion. (C) 1996 Academic Press, Inc.