How Many Needles are in a Haystack, or how to Solve #P-Complete Counting Problems Fast

This IOE talk may be of special interest to computer scientists.
We present a new generic randomized algorithm for approximating
quite general #P-complete counting problems, like satisfiability, the
number of Hamiltonian cycles in a graph, the permanent, and the
number of
self-avoiding walks of certain length. To do so we cast the
underlying counting problem into an associate rare-event
probability estimation one, and then apply the cross-entropy (CE) and
the
MinxEnt methods for updating the parameters of the importance
sampling (IS)
distribution. We use importance sampling to speed up the
simulation process and, thus to produce a low variance estimate of
the desired counting quantity. We establish convergence of our
algorithm for some particular #P-complete counting problems and
present supportive numerical results, which strongly suggest that the
presented algorithm has polynomial complexity in the size of the
problem.