Hardness of approximation for counting problems
Someone just asked me about hardness of approximation results for counting problems. Good question. Off the top of my head, I would say the following...
For some counting problems there is a) a straightforward notion of a random input, and b) a polytime algorithm for checking the property. For example, consider #3SAT -- Given a formula, how many satisfying assignments does it have? Or, what fraction of all assignments from {0,1}^n are satisfying?
For such a problem you can efficiently estimate the answer to within any additive 1/poly(n) in polynomial time, by random sampling: Just pick a bunch of assignments at random, check if they are satisfying, and compute the empirical fraction. It will be additively very close, with high probability.
Note that this is not the "usual" sort of approximation-algorithm guarantee we are looking for; we have been looking at multiplicative guarantees. It's easy to see that for #3SAT no multiplicative factor guarantee is possible: For suppose A always returned an estimate p such that p/C <= true fraction of satisfying assignments <= Cp (where C is anything). Then A could be used to solve 3SAT: when the instance is unsatisfiable A must return 0 and when it is satisfiable it must return a number which is at least 2^{-n}/C. Hence we can distinguish.
Other types of counting problems don't have the above-mentioned two properties. A classic example is #PerfectMatchings -- given a bipartite graph, count the number of perfect matchings in it. (This is equivalent to the "Permanent" problem.) A famous result from four years ago by Jerrum, Sinclair, and Vigoda --
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
-- gives a PTAS for this problem. (I.e., it can efficiently return a multiplicative (1+eps)-factor estimate for any constant eps > 1/poly(n).)
Naturally, therefore, there is no hardness-of-approximation result for the #PerfectMatching problem!
In fact, I can't think of a counting problem with an interesting hardness of approximation result. Does anybody know one?
For some counting problems there is a) a straightforward notion of a random input, and b) a polytime algorithm for checking the property. For example, consider #3SAT -- Given a formula, how many satisfying assignments does it have? Or, what fraction of all assignments from {0,1}^n are satisfying?
For such a problem you can efficiently estimate the answer to within any additive 1/poly(n) in polynomial time, by random sampling: Just pick a bunch of assignments at random, check if they are satisfying, and compute the empirical fraction. It will be additively very close, with high probability.
Note that this is not the "usual" sort of approximation-algorithm guarantee we are looking for; we have been looking at multiplicative guarantees. It's easy to see that for #3SAT no multiplicative factor guarantee is possible: For suppose A always returned an estimate p such that p/C <= true fraction of satisfying assignments <= Cp (where C is anything). Then A could be used to solve 3SAT: when the instance is unsatisfiable A must return 0 and when it is satisfiable it must return a number which is at least 2^{-n}/C. Hence we can distinguish.
Other types of counting problems don't have the above-mentioned two properties. A classic example is #PerfectMatchings -- given a bipartite graph, count the number of perfect matchings in it. (This is equivalent to the "Permanent" problem.) A famous result from four years ago by Jerrum, Sinclair, and Vigoda --
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
-- gives a PTAS for this problem. (I.e., it can efficiently return a multiplicative (1+eps)-factor estimate for any constant eps > 1/poly(n).)
Naturally, therefore, there is no hardness-of-approximation result for the #PerfectMatching problem!
In fact, I can't think of a counting problem with an interesting hardness of approximation result. Does anybody know one?
posted by Ryan O'Donnell at 1:27 PM
1 Comments:
A paper called "On the hardness of approximate reasoning" has some hardness of approximation results for counting 2CNF satisfying assignments and related problems.
http://l2r.cs.uiuc.edu/~danr/Papers/hardJ.pdf
Note that the hardness results are *NP-hardness* even though we are dealing with couting problems. One cannot expect say #P-completeness since approximate counting is in BPP^{NP} and thus in the third level of polynomial hierarchy (a result by Larry Stockmeyer, 1983).
Post a Comment
<< Home