This paper, originally presented at IJCAI 2015, explores the computational boundaries of Belief Revision—the process of updating a knowledge base with new, potentially conflicting information while maintaining consistency and "minimality."
Introduction and Problem Definition
In Artificial Intelligence, agents must constantly update their beliefs ($T$) when they receive new information ($\phi$). Following Satoh’s operator, this involves finding models of the new information that are "closest" (in terms of set-inclusion of differing variables) to the original models.
Reasoning over these revised beliefs is computationally brutal; it typically sits at the second level of the polynomial hierarchy ($\Pi^P_2$-complete), making it significantly harder than standard SAT problems. The authors aim to identify "islands of tractability" where belief revision becomes manageable by using parameterized complexity, which examines how specific features of the input (parameters) affect runtime.
Methodology
The authors employ parameterized complexity theory to analyze Satoh’s revision operator through several lenses:
- Backdoor Sets: They generalize results for Horn formulas by looking at "backdoors"—small sets of variables that, once assigned, simplify a complex formula into a Horn formula.
- Treewidth Analysis: They test whether structural simplicity (low treewidth) in the knowledge base and the revision formula independently is sufficient for efficiency.
- Shared Variables: They introduce a novel parameter: the cardinality of the set of variables shared between the knowledge base $T$ and the revision formula $\phi$ ($|S|$).
- Algorithm Design: They provide a generic fixed-parameter tractable (FPT) algorithm that leverages these shared variables and can incorporate existing SAT-solving techniques for individual components.
Key Insights and Results
The paper establishes a detailed landscape of complexity, showing where the problem remains hard and where it becomes tractable. A central finding is that structural measures like treewidth often fail when applied independently; for instance, even if $T$ and $\phi$ both have a treewidth of 1, the problem remains para-coNP-hard.
However, the interaction between the old and new information—the "Shared Variable" bridge—is a powerful lever. If the knowledge base and the update only "talk" to each other through a small number of variables, the problem becomes much easier. Theorem 7 states that if SAT is efficient for the knowledge base and update separately, and they share few variables, the entire process is FPT.
Summary of Findings:
- Backdoor Success: Revision is FPT when parameterized by the size of the Horn-backdoor of $T$ plus the number of variables in $\phi$.
- Treewidth Failure: Proved that $tw(T) + tw(\phi)$ is para-coNP-hard, meaning structural simplicity in the parts does not translate to simplicity in the whole.
- A New Complexity Class: Bounding only shared variables (without assuming individual formulas are easy) makes the problem complete for $FPT^{NP}[f(k)]$, solvable by an FPT algorithm with limited NP oracle calls.
Limitations and Future Work
The results focus specifically on Satoh’s operator. Other popular operators, such as Dalal’s (which uses Hamming distance rather than set inclusion), might present different complexity landscapes. Additionally, the shared-variable algorithm assumes the query ($\psi$) is of constant size. Future research may investigate whether these insights apply to other belief change formalisms, such as belief merging or contraction.
Summary updated