Enumerative counting is hard

AbstractAn n-variable Boolean formula may have anywhere from 0 to 2n satisfying assignments. Can a polynomial-time machine, given such a formula, reduce this exponential number of possibilities to a small number of possibilities? We call such a machine an enumerator and prove that if there is a good polynomial-time enumerator for #P (i.e., one where for every Boolean formula f, the small set has at most O(|f|1−ε) numbers), then P = NP = P# P and probabilistic polynomial time equals polynomial time. Furthermore, we show that #P polynomial-time Turing reduces to enumerating #P