7
$\begingroup$

#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?

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

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.