|
Abstract : |
We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. Counterfactual implication p? q models a statement "if p, then q, " where p is known or expected to be false, and is different from material implication p) q. A nested counterfactual is a counterfactual statement where the conclusion q is a (possibly negated) counterfactual. Statements of the form p 1? (p 2? \Delta \Delta \Delta (p n? q) \Delta \Delta \Delta) intuitively correspond to hypothetical queries involving a sequence of revisions. We show that evaluating such statements is \Pi P 2-complete, and that this task becomes PSPACE-complete if negation is allowed in the nesting. We also consider nesting a counterfactual in the premise, i.e. (p? q) ? r and show that evaluating such statements is most likely much harder than evaluating p? (q? r)., |
