An analysis of Monte Carlo algorithms for counting problems (Q1083200)

The efficiency of Monte Carlo approximations for solving {\#}P-hard counting problems is investigated in this paper. In particular, a necessary condition is derived for a problem to admit of a Monte Carlo algorithm with polynomial time complexity and bounded relative error. Two Monte Carlo procedures are proposed for the approximate solution of the following {\#}P-complete counting problems: given a finite set E and a collection \(\{S_ 1,S_ 2,...,S_ m\}\) of subsets of E, compute the cardinality of the union set \(\cup^{m}_{i=1}S_ i\) (Union Cardinality Problem) or the intersection set \(\cap^{m}_{i=1}S_ i\) (Intersection Cardinality Problem). Tight bounds on the worst-case time complexity of both algorithms are explicitly obtained. It is shown that one of the algorithms solves the union cardinality problem in polynomial time, within any specified accuracy level, provided \(m<4| E|\), the cardinalities of the sets \(S_ i\), \(i=1,2,...,m\), are known in advance and it is possible to select a member of \(S_ i\) in polynomial time. Observe that these requirements are fulfilled in all relevant applications of the union cardinality problem. Finally, a probabilistic analysis of the proposed algorithm for the intersection cardinality problem is developed, assuming a reasonable stochastic model over the instances of the problem. This allows to show that, under mild assumptions on the stochastic parameters, a substantial reduction in running time can be achieved with probability tending to one when the input size grows asymptotically large.