At the heart of artificial intelligence lies a fundamental tension: an agent must update its knowledge when faced with new evidence, but doing so rationally is often computationally intractable. This field, rooted in the Alchourrón, Gärdenfors, and Makinson (AGM) paradigm, seeks to balance the logical ideal of "minimal change" with the practical constraints of real-time systems.
The Search for Minimal Change
The core difficulty of belief revision stems from the principle of informational economy. When new information contradicts an existing knowledge base, an agent should not simply discard everything it knows. Instead, it must find a new state that incorporates the new data while retaining as much of the old information as possible.
Jon Doyle established that finding this optimal or minimal update is an NP-hard challenge. The intuition is that "minimal change" is essentially a search problem over an exponential space of possible world states or subsets of beliefs. To maintain consistency, the system must identify which specific beliefs to retract to resolve a contradiction—a task that mirrors the complexity of the Boolean satisfiability problem (SAT). As Doyle argues, the desire for a perfectly conservative update creates a direct conflict with the requirements of real-time performance.
The Complexity of Post-Revision Inference
Even if an agent successfully updates its beliefs, the trouble does not end there. The resulting knowledge base must still be useful for reasoning. Liberatore et al. demonstrated that performing inference on a knowledge base after a revision or update is generally coNP-hard.
This remains true even when the initial information is represented in simple logical formats, such as binary clauses. The process of maintaining consistency during an update introduces a layer of overhead that persists into every subsequent query. This suggests that the "cost" of belief revision is not a one-time fee paid during the update, but a permanent tax on the system's reasoning capabilities.
Climbing the Polynomial Hierarchy
As the reasoning tasks become more sophisticated, the complexity climbs higher into the polynomial hierarchy. For instance, Jérôme Lang notes that many established belief update operators reach $\Pi^p_2$-complete complexity. This level of difficulty arises because these operators often involve nested layers of quantification—essentially asking, "Is it true that for all closest possible worlds, a certain property holds?"
The complexity becomes even more daunting in specialized domains:
- Action Descriptions: When updating causal laws in an action domain, Eiter et al. found that finding an optimal update is $\Sigma^P_3$-complete. This reflects the difficulty of reconciling conflicting causal rules while satisfying behavioral constraints.
- Conditional Beliefs: Updating "if-then" rules rather than simple facts requires navigating plausibility orderings. Boutilier et al. explain that determining which rules conflict with a new conditional often requires an exponential number of satisfiability tests.
- Iterated Revision: When an agent must process a sequence of hypothetical "what-if" scenarios, the complexity can jump to PSPACE-complete, as shown in The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions.
Algorithmic Strategies for Scalability
Despite these daunting theoretical bounds, recent research has focused on making belief revision practical for real-world applications. The goal is to find structures or algorithms that can bypass the worst-case complexity.
One approach is to limit the "ripple effect" of an update. Wu et al. explore relevance-based belief change and language splitting, which attempt to isolate the update to only the relevant portion of the knowledge base. By partitioning the logic, the system avoids re-evaluating unrelated beliefs, though even within these restricted frameworks, tasks often remain coNP-hard.
Another direction involves leveraging modern solver technology. Hunter et al. introduced GenC, a tool that uses AllSAT solvers and parallel processing to handle belief revision. Their work demonstrates that by using efficient computational methods, systems can scale to handle hundreds of variables and millions of clauses, achieving runtimes in seconds. This represents a shift from purely axiomatic research toward the development of production-ready systems that can handle the high-dimensional evidence sets required by modern AI.
Finally, some specific models offer better efficiency by design. Chatterjee et al. show that in Multiple-Environment Markov Decision Processes (MEMDPs), belief updates can be achieved in linear time relative to the state space. While the total number of potential environments can still be a bottleneck, such frameworks provide a path toward real-time performance in complex scenarios like robot navigation.
Key Foundational Work
The Ins and Outs of Reason Maintenance (1983) — contributed 2 concept elements to this direction.