THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION
命题知识库更新的算法及其复杂性

This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge base have been proposed recently by several researchers, some are formula--based methods and the others are model-based methods, but all methods are intractable in the general case. This paper discusses a formula-based method-Ginsberg's method, and presents a polynomial algorithm when the number of formulas is far less than the number of variables.