R-calculus is a formal revision calculus system which can formally deduce R-contraction. R-contraction is the axiom system's maximal subset that is consistent with the refutations by facts. In this paper, we prove that computing R-contraction for propositional logic is hard by two steps. Firstly, we prove that computing R-contraction is at least as hard as its decision problem. Secondly, we prove that the decision problem of computing R-contraction is NP-complete by presenting that the satisfiability problem, a known NP-complete problem, can polynomially reduce to it. So for this problem, we should direct our efforts at developing efficient heuristic algorithms or some other technology such as human-computer interaction.