In this paper, the computational complexity of propositional clause set counter-factuals is discussed. It is shown that the computational complexity of propositional clause setcounterfactuals is at the second level of the polynomial hierarchy, and that the computationalcomplexity of propositional H clause set counterfactuals is at the first level of the polynomialhierarchy. Furthermore, some polynomial algorithms are presented for some special propositionalclause set, such as the unique satisfiable clause set and the clause set of which only one subset isminimally inconsistent with the input clause whose inconsistency check can be solved in polynomialtime.