摘要：Problem SUCP is the problem to calculate the size of the union of n Cartesian products. SUCP contains as a special case the problem of counting the number of unsatisfying assignments of the satisfiability problem (SAT). Therefore, SUCP is NP-hard and, in further detail, P-complete. We presented an exact algorithm to solve SUCP, called the grouping method, and analyzed its average running time. Except for this, SUCP has been hardly studied so far. In this paper, we analyze the average running time of a backtracking algorithm to solve SUCP. For the analysis, S are constructed by randomly selecting each element from set D with probability p. We show its average running time. For the same instances, the average running time of the grouping method is determined and that of the naive method. These results indicate that the backtracking algorithm is most efficient under specific conditions
