11
$\begingroup$

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$)?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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