The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. 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).
@inproceedings{ijcai1993p74,
title = {The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions},
author = {Eiter, Thomas and Gottlob, Georg},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {526--532},
year = {1993},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1993/74},
}
TY - CPAPER TI - The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions AU - Eiter, Thomas AU - Gottlob, Georg T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 526 EP - 532 UR - https://ijcai.org/proceedings/1993/74 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
