---
title: "The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions"
authors:
  - "Thomas Eiter"
  - "Georg Gottlob"
doi: ""
url: "https://ijcai.org/proceedings/1993/74"
pdf: "https://ijcai.org/proceedings/1993/0074.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "526-532"
track: "Knowledge Representation"
keywords:
---

# The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

Thomas Eiter, Georg Gottlob

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 526-532.

## 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 pis 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 > · · · (Pn > q) · · ·) intuitively correspond to hypothetical queries involving a sequence of revisions. We show that evaluating such statements is IIf-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).