The Complexity of Model Checking for Belief Revision and Update

AAAI 1996

TL;DR

This paper dives into the computational complexity of "model checking" for belief revision and update systems. It reveals that checking if a specific world state (a model) is consistent with updated knowledge is often significantly harder than traditional logical inference, and surprisingly, the complexity can vary greatly between different revision operators.

What Problem Does This Paper Address?

In artificial intelligence, we often need to represent an agent's knowledge about the world. This knowledge isn't static; it changes as new information arrives. When new information contradicts existing beliefs, the agent must revise its knowledge base. This paper focuses on two key ways this happens: belief revision (incorporating new, possibly contradictory, information) and belief update (incorporating new information that describes a changed state of the world).

A core challenge is how to formally model these processes. Researchers have developed various operators (like Ginsberg's, Winslett's, Dalal's, etc.) to define how a knowledge base T should be modified when a new piece of information P arrives, resulting in a new knowledge base T*P or TWP.

While much work has focused on defining what the revised knowledge base is, this paper tackles a crucial computational question: Given a knowledge base T, a new piece of information P, and a specific state of the world (represented as a model M), is M a valid model of the revised knowledge base T*P? This is known as "model checking." The authors highlight that this problem is fundamental for knowledge representation formalisms that use model-based representations, where reasoning is done by examining models rather than just manipulating formulas. They aim to understand the computational cost of this model checking task for various existing belief revision and update operators.

Methods

The paper analyzes the computational complexity of model checking for several prominent belief revision and update operators. They categorize these operators into formula-based (operating directly on the logical formulas) and model-based (operating on the sets of possible worlds, or models, that satisfy the knowledge base).

The core methodology involves classifying the difficulty of the model checking problem using standard complexity classes from the polynomial hierarchy (P, NP, coNP, Σ², Π², etc.). They analyze how the complexity changes under different conditions, such as when the knowledge base and the new information are restricted to Horn clauses (a simpler form of propositional logic) or when the size of the new information P is bounded by a constant.

The authors present a table summarizing the complexity results for various operators under different scenarios (general case, Horn case, bounded P). They also provide proof sketches for some key theorems, illustrating how to construct algorithms or reductions to establish membership in specific complexity classes.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Model Checking is Harder Than Inference: A major finding is that for many belief revision operators, the complexity of model checking (M |= T*P?) is significantly higher than the complexity of traditional query inference (T*P |= Q?). This challenges the intuition that these tasks should be similarly difficult.
  • Operator-Specific Complexities: The paper reveals that different revision operators, even those that are logically equivalent in terms of their inference capabilities, can have vastly different complexities for model checking. This suggests that the choice of operator has practical implications for computational feasibility.
  • The "Minimal Change" Trade-off: The core idea behind revision is "minimal change." The paper implicitly shows that achieving this minimal change while maintaining consistency can lead to computationally expensive checks for specific world states.
  • Bounded P Offers Tractability: A significant insight is that if the new piece of information P is small (bounded by a constant), the model checking complexity for many operators drops dramatically, often to polynomial time. This suggests that practical applications might be feasible if new information is typically concise.
  • Horn Clauses Help, But Not Always: Restricting the knowledge base and new information to Horn clauses generally reduces complexity, but there are exceptions (like Dalal's operator) where this simplification doesn't yield the same benefits, likely due to the operator's reliance on cardinality-based measures.

Key Results

The paper presents a detailed complexity analysis, summarized in a comprehensive table (Figure 1). Key results include:

  • General Case: For most operators (e.g., Forbus, Winslett, Satoh, Borgida), deciding M |= T*P is Σ²-complete. This is a high complexity level within the polynomial hierarchy.
  • Ginsberg's Operator: Surprisingly, Ginsberg's revision operator (*G) is coNP-complete for model checking, which is simpler than many other operators, despite its inference problem being II-complete.
  • Dalal's Operator: Dalal's operator (*D) is PNP[O(log n)]-complete, making it relatively easier than many others.
  • Bounded P: When |P| <= k (constant), model checking for most operators (*F, *W, *H, *G, *B, *S, *D, *Web) becomes polynomial or coNP-complete, indicating a significant practical advantage.
  • Horn Case: In the Horn case, complexities generally decrease. For instance, *G and *H become polynomial, while *s, *w, *B become NP-complete.

Limitations and Future Work

  • Focus on Propositional Logic: The analysis is confined to propositional logic. Extending these results to first-order logic or other richer formalisms would be a significant next step.
  • Specific Operators: While many key operators are covered, there are other belief revision and update formalisms that could be analyzed.
  • Theoretical vs. Practical: The paper focuses on theoretical complexity. While the "bounded P" result offers practical hope, further research could explore efficient algorithms and heuristics for the intractable cases.
  • Model-Based vs. Formula-Based: The paper notes that while formula-based and model-based approaches have different underlying mechanisms, their complexity results can be surprisingly similar or different, suggesting deeper connections to be explored. The authors suggest that understanding the interplay between these approaches and their computational implications is an ongoing area of research.

Summary updated

BibTeX
@inproceedings{1996complexity,
  title = {{The Complexity of Model Checking for Belief Revision and Update}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure