Abstract
In artificial intelligence, reasoning about hypothetical scenarios—counterfactuals—is essential for tasks such as diagnosis, planning, and common-sense reasoning. While evaluating a single counterfactual is well-understood, real-world scenarios often involve nested "what-if" questions. This paper investigates the computational complexity of evaluating these nested counterfactuals over propositional knowledge bases using Ginsberg’s "possible worlds" approach. We demonstrate that while sequential revisions (right-nesting) remain within the second level of the polynomial hierarchy ($\Pi^p_2$-complete), the introduction of negation or the use of counterfactuals within premises (left-nesting) significantly increases complexity to PSPACE-complete and $\Pi^p_4$-complete levels, respectively.
Introduction
Counterfactual reasoning involves evaluating statements about scenarios that are known to be false, typically formulated as "If $p$ were true, then $q$ would be true" ($p > q$). Unlike material implication ($p \to q$), counterfactuals require a revision of the current knowledge base (KB). The standard evaluation method is the Ramsey Test: to determine if $p > q$ holds, one must minimally modify the KB to accommodate $p$ and then check if $q$ is a logical consequence of the revised KB.
In complex AI systems, reasoning is rarely limited to a single hypothetical. Systems must often handle iterated revisions (e.g., "If $p_1$ happened, and then $p_2$ occurred...") or nested conditions (e.g., "If it were the case that $p$ leads to $q$, then $r$ would follow"). This paper provides a rigorous complexity-theoretic mapping of these nested structures.
Categorizing Nested Counterfactuals
The authors distinguish between three primary forms of nesting:
- Right-Nested Counterfactuals: Statements of the form $p_1 > (p_2 > \dots (p_n > q))$. These represent a sequence of hypothetical updates to a knowledge base.
- Right-Nested with Negation: Statements where negation is allowed within the nesting, such as $p > \neg(q > r)$.
- Left-Nested Counterfactuals: Statements of the form $(p > q) > r$, where a counterfactual statement serves as the premise for another.
Computational Complexity Results
The research utilizes the Polynomial Hierarchy and PSPACE to categorize the difficulty of these reasoning tasks.
The Stability of Sequential Revision
A significant finding of this work is that simple right-nesting does not increase the complexity of the problem beyond that of a single counterfactual. Evaluating $p_1 > (p_2 > \dots (p_n > q))$ is $\Pi^p_2$-complete. This suggests that for AI agents, performing a sequence of hypothetical revisions is computationally no more demanding than performing one, provided no negations are involved. The authors provide the RNCF algorithm to demonstrate this upper bound.
The Impact of Negation
The computational landscape shifts dramatically when negation is introduced into right-nested structures. The authors prove that evaluating such statements is PSPACE-complete. This jump indicates that the problem becomes as difficult as any problem solvable with polynomial memory, likely requiring exponential time in practice. Negation forces the system to consider a much broader range of "possible worlds," leading to this explosion in complexity.
The Difficulty of Premise Nesting
Left-nested counterfactuals—where the condition itself is a hypothetical—are even more difficult to evaluate than right-nested ones. The authors show that $(p > q) > r$ is $\Pi^p_4$-complete. This high level of complexity stems from the nonmonotonic nature of counterfactuals: a small change in a nested premise can lead to a radically different set of "closest possible worlds," making the evaluation of the outer counterfactual extremely sensitive and computationally expensive.
Tractable Subsets: Horn Clauses
To find more manageable versions of these problems, the authors examine Horn clauses (propositional formulas with at most one positive literal). When the knowledge base and all premises are restricted to Horn logic, the complexity of right-nested counterfactuals drops to coNP-complete. In certain restricted cases, the problem even becomes solvable in polynomial time, offering a potential path for practical implementation in specialized domains.
Conclusion
This research establishes a clear hierarchy of difficulty for nested counterfactual reasoning. While iterated belief revision is surprisingly manageable ($\Pi^p_2$), the inclusion of negation or nested premises pushes the requirements into PSPACE and higher levels of the polynomial hierarchy. These results provide a roadmap for AI researchers to understand the computational costs associated with different types of hypothetical reasoning.
Reference: Eiter, T., & Gottlob, G. (1993). The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions. Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI).
Summary updated