♯P-complete

As a non-example, consider the case of counting solutions to a 1-satisfiability problem: a series of variables that are each individually constrained, but have no relationships with each other.

The solutions can be efficiently counted, by multiplying the number of options for each variable in isolation.

[3] There are probabilistic algorithms that return good approximations to some #P-complete problems with high probability.

Many #P-complete problems have a fully polynomial-time randomized approximation scheme, or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required.

Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.