The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions
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 p1 >(p2 > ...(pn > q)...) intuitively correspond to hypothetical queries involving a sequence of revisions. We show that evaluating such statements is Π2p complete, and that this task becomes PSPACE-cornplete 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).
Cite
Text
Eiter and Gottlob. "The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions." International Joint Conference on Artificial Intelligence, 1993. doi:10.1006/jcss.1996.0083Markdown
[Eiter and Gottlob. "The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions." International Joint Conference on Artificial Intelligence, 1993.](https://mlanthology.org/ijcai/1993/eiter1993ijcai-complexity/) doi:10.1006/jcss.1996.0083BibTeX
@inproceedings{eiter1993ijcai-complexity,
title = {{The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions}},
author = {Eiter, Thomas and Gottlob, Georg},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1993},
pages = {526-533},
doi = {10.1006/jcss.1996.0083},
url = {https://mlanthology.org/ijcai/1993/eiter1993ijcai-complexity/}
}