Forgetting in short and heterogeneous sequences of belief revisions
This work addresses computational complexity problems in belief revision for AI and knowledge representation, with incremental theoretical contributions.
The paper investigates the computational complexity of forgetting specific belief revision episodes in sequences, proving coNP-hardness for certain cases and presenting a polynomial algorithm for two lexicographic Horn revisions. It also enhances hardness results for heterogeneous sequences to Dp-hardness.
Forgetting a specific belief revision episode may not erase information because the other revisions may provide or entail the same information. Whether it does was proved coNP-hard for sequences of two arbitrary lexicographic revisions or arbitrarily long lexicographic Horn revisions. A polynomial algorithm is presented for the case of two lexicographic Horn revision. Heterogeneous sequences, including revisions other than lexicographic, were proved to belong in Delta2. Their previously proved coNP-hardness is enhanced to Dp-hardness.