# Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete.

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

## 2 Answers

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.)

Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #P paper [2]) but, relaxing your requirement a little, there's an FPRAS due to Jerrum and Sinclair [1]. This corresponds to counting perfect matchings in bipartite graphs.

References

[1] Mark Jerrum and Alistair Sinclair, "Approximating the permanent." SIAM Journal on Computing, 18(6):1149–1178, 1989. (PDF)

[2] Leslie Valiant, "The complexity of computing the permanent." Theoretical Computer Science, 8:189–201, 1979. (PDF)

[3] Dror Weitz, "Counting independent sets up to the tree threshold." STOC 2006. (Unpublished full version: PDF.)

Adding another example I came across, with an even stronger result:

A (deterministic) FPTAS exists for the problem of counting the number of matchings in a bounded-degree bipartite graph, while this is a $\#P$-complete problem.