What are the current best upper bounds of #P?

#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP.

I'm wondering if there have been any studies on the worst-case behaviors of current best solutions to problems in NP. My focus in the past has been on 3-SAT, so I am particularly interested in the time it takes to count 3-SAT solutions in the worst case. However, I ask in general, What are the current best upper bounds for any (#P-complete) problem in #P?

• Do you mean upper bounds for #P-complete problems? Because otherwise you can cook up problems in #P that are trivial to solve. – Mahdi Cheraghchi Jun 18 '13 at 21:35
• @MCH: Yes, I mean #P-complete problems. – Matt Groff Jun 18 '13 at 21:52
• What about PTASs for the permanent ? is that an example ? – Suresh Venkat Jun 19 '13 at 0:29
• @SureshVenkat: I'd prefer not to include approximations. Perhaps as a separate question, but I'm really interested in exacting answers. – Matt Groff Jun 19 '13 at 1:17

2 Answers

One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.

I you’re looking for natural problems, you can compute many counting problems on planar graphs in time $\exp(\sqrt n)$ because of the planar separator theorem. For example, everything that can be expressed as a valuation of the Tutte polynomial [1]. Most of these problems remain #P-hard restricted to planar graphs, see Tutte Polynomial @ Wikipedia.

[1] K. Sekine, H. Imai, S. Tani, Computing the Tutte polynomial of a graph of moderate size, Algorithms and Computation, 6th International Symposium (ISAAC ’95), Cairns, Australia, December 4–6, 1995, Lecture Notes in Computer Science 1004, Springer, 1995, pp. 224–233.