<p>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 <a href="http://en.wikipedia.org/wiki/Tutte_polynomial">Tutte Polynomial @ Wikipedia</a>. </p>

<p>[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.</p>

CC BY-SA 3.0
2013-06-19T07:04:04.347Z
2013-06-19T09:44:30.997Z
2013-06-19T09:44:30.997Z
Thore Husfeldt
<p>One such algorithm for $\#3\operatorname{SAT}$ is due to <a href="http://www.itu.dk/people/konk/papers/%233-sat.pdf">Kutzkov</a>.</p>

CC BY-SA 3.0
2013-06-19T06:32:58.167Z
2013-06-19T09:24:50.547Z
2013-06-19T09:24:50.547Z
Andreas Björklund
<p><a href="http://en.wikipedia.org/wiki/Sharp-P" rel="nofollow">#P</a> 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.</p>

<p>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, <strong>What are the current best upper bounds for any (#P-complete) problem in #P?</strong></p>

CC BY-SA 3.0
2013-06-18T21:35:17.857Z
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
CC BY-SA 3.0
2013-06-18T21:52:45.453Z
@MCH: Yes, I mean #P-complete problems.
Matt Groff
CC BY-SA 3.0
2013-06-19T00:29:27.177Z
What about PTASs for the permanent ? is that an example ?
Suresh Venkat
CC BY-SA 3.0
2013-06-19T01:17:34.793Z
@SureshVenkat: I'd prefer not to include approximations.  Perhaps as a separate question, but I'm really interested in exacting answers.
Matt Groff
<ds.algorithms><sat><counting-complexity><upper-bounds><worst-case>
What are the current best upper bounds of #P?
Matt Groff
# What are the current best upper bounds of #P?

(Asked by: username_0 on 2013-06-18)

[#P](http://en.wikipedia.org/wiki/Sharp-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?**

**Tags:** ds.algorithms, sat, counting-complexity, upper-bounds, worst-case

> **Comments:**
> **username_1**: Do you mean upper bounds for #P-complete problems? Because otherwise you can cook up problems in #P that are trivial to solve.  
> **username_0**: @MCH: Yes, I mean #P-complete problems.  
> **username_2**: What about PTASs for the permanent ? is that an example ?  
> **username_0**: @SureshVenkat: I'd prefer not to include approximations.  Perhaps as a separate question, but I'm really interested in exacting answers.  

---

## 2 answers

### Answer by username_4 on 2013-06-19. Score: 11 | Accepted answer

One such algorithm for $\#3\operatorname{SAT}$ is due to [Kutzkov](http://www.itu.dk/people/konk/papers/%233-sat.pdf).


---

### Answer by username_3 on 2013-06-19. Score: 9

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](http://en.wikipedia.org/wiki/Tutte_polynomial).

[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.


---

