A note on enumerative counting
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)].
- Addendum to: Non-deterministic exponential time has two-prower interactive protocols
- Bounded queries to SAT and the Boolean hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Enumerative counting is hard
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 4064488 (Why is no real title available?)
- scientific article; zbMATH DE number 48150 (Why is no real title available?)
- On Approximation Algorithms for # P
- Structural complexity theory: Recent surprises
- The complexity of computing the permanent
- The Complexity of Enumeration and Reliability Problems
- On the power of enumerative counting
- On the hardness of computing the permanent of random matrices
- Some connections between bounded query classes and non-uniform complexity.
- Enumerative counting is hard
- Tally NP sets and easy census functions.
- Optimal series-parallel trade-offs for reducing a function to its own graph
- A new way of counting \(n^ m\)
- The enumerability of P collapses P to NC
- An Introduction to Enumeration
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- On Approximation Algorithms for # P
- Reconstructing Algebraic Functions from Mixed Data
- Counting CTL
- Reductions to sets of low information content (extended abstract)
- Enumerations of the Kolmogorov function
- The Enumeration Methods of Redfield
- Toward a Theory of Enumerations
- The communication complexity of enumeration, elimination, and selection
- Permanental rank vs determinantal rank of random matrices over finite fields
This page was built for publication: A note on enumerative counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809598)
