The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

摘要

We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. A counterfactualp>qis a conditional query with the meaning “Ifpwould be true in the knowledge base, would it then hold that alsoqis true,” which is different from material implicationp⇒q. A nested counterfactual is a counterfactual statement where the premisepor the conclusionqis a counterfactual. Statements of the formp1>(p2…(pn>q)…) intuitively correspond to conditional queries involving a sequence of revisions. We show that evaluating such statements isΠP2-complete and that this task becomes PSPACE-complete if negation is allowed in a nesting of this form. We also consider nesting a counterfactual in the premise, i.e., (p>q)>r, and show that evaluating such statements isΠP4-complete, thus most likely much harder than evaluatingp>(q>r). Finally, we also address iterated nestings in the premise and the mix of nestings in the premise and the conclusion.