Procedures for the CPA problem based on the elimination of Boolean constraints

In this paper we investigate the computational problem CPA, a variant of PSAT, about the coherence of a probability assessment. After the formalization of the problem, we make a survey of recent results that have produced a set of simplication rules to adopt in an algorithm for checking the coherence. The average complexities of the algorithm for the specic subproblem 2CPA has been already shown to be polynomial, and now we are able to compute the complexity also for the the worst case of the same subproblem.