Technical Report No. 83, July 1996 - Abstract

Nebel, Bernhard:
How Hard is it to Revise a Belief Base?

If a new piece of information contradicts our previously held beliefs, we have to revise our beliefs. This problem of belief revision arises in a number of areas in Computer Science and Artificial Intelligence, e.g., in updating logical database, in hypothetical reasoning, and in machine learning. Most of the research in this area is influenced by work in philosophical logic, in particular by Gärdenfors and his colleagues, who developed the theory of belief revision}. Here we will focus on the computational aspects of this theory, surveying results that address the issue of the computational complexity of belief revision.