Fast Algorithms for Revision of Some Special Propositional Knowledge Bases

In this paper, the computational complexity of propositional clause set counterfactuals is discussed. It is shown that the computational complexity of propositional clause set counterfactuals is at the second level of the polynomial hierarchy, and that the computational complexity of propositional Horn clause set counterfactuals is at the first level of the polynomial hierarchy. Furthermore, some polynomial algorithms are presented for some special propositional clause set, such as the unique satisfiable clause set and the clause set of which only one subset is minimally inconsistent with the input clause whose inconsistency check can be solved in polynomial time. This work is supported by the National Natural Sciences Foundation of China under Grant Nos.60033020 and 60103020 and the China Postdoctoral Foundation of Sciences.