patternMinor
Does #$P$-Completeness imply approximation hardness?
Viewed 0 times
implyapproximationhardnesscompletenessdoes
Problem
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$)?
Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
Solution
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.)
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.)
Context
StackExchange Computer Science Q#28672, answer score: 9
Revisions (0)
No revisions yet.