Enumerative counting is hard
Jin‐Yi Cai, Lane A. Hemachandra · Information and Computation · 1989
An n -variable Boolean formula may have anywhere from 0 to 2 n 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.