On the power of enumerative counting (Q1199550)

We study the functions in \(\#P\), which have polynomial time enumerators. We show that functions in \(\#P\), which have polynomial time enumerators are low for the counting class \(PP\). As a corollary, it follows that functions hard for \(\#P\) under polynomial time reductions do not have enumerators unless the counting hierarchy collapses in \(PP\). We also construct relativisations in which for any polynomial \(p(n)\), there are functions in \(\#P\), which have enumerators with output size \(p(n)+1\), but not enumerators with output size \(p(n)\).