Fast Algorithms for Revision of Some Special Propositional Knowledge Bases

In this paper, the computationalcomplexity of propositional clause set counterfactuals is discussed. Itis shown that the computational complexity of propositional clause setcounterfactuals is at the second level of the polynomial hierarchy, andthat the computational complexity of propositional Horn clause setcounterfactuals is at the first level of the polynomial hierarchy.Furthermore, some polynomial algorithms are presented for some specialpropositional clause set, such as the unique satisfiable clause set andthe clause set of which only one subset is minimally inconsistent withthe input clause whose inconsistency check can be solved in polynomialtime.