A note on enumerative counting (Q809598): Difference between revisions

The authors show that {\#}P cannot be enumeratively approximated unless every {\#}P-function is computable in polynomial time. An enumerative approximation of a function f is a polynomial time computable function g such that g(x) computes a list of numbers containing f(x) as one of its members. In their proof the authors show how to construct from any given enumerative approximation of {\#}SAT a polynomial-time algorithm for {\#}SAT. This algorithm uses manipulations of permanents exploiting the fundamental result of \textit{L. G. Valiant} [Theor. Comput. Sci. 8, 189-201 (1979; Zbl 0415.68008)] that permanent evaluation is {\#}P-hard. As the authors remark a different proof of their result has been given independently by \textit{S. Toda} building upon an approach of \textit{R. Amir, R. Beigel} and \textit{W. Gasarch} [Structure in Complexity Theory, IEEE Computer Society Press, 232-243 (1990)].