5
$\begingroup$

Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:

For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs a number $k$ such that $(1 -\varepsilon) \cdot \#f \leq k \leq (1 + \varepsilon) \cdot \# f$ with probability at least $1 - \varepsilon$.

I've seen this method referred to as hashing-based counting.

On the other hand, as far as I can tell, the algorithm described in Theorem 6.4 in the Jerrum-Valiant-Vazirani paper [2] can also be used to approximate a #P function by making a polynomial number of calls to an almost uniform, but not necessarily polynomial-time, generator of solutions to the NP counterpart of the #P function to be evaluated (with a subtlety regarding self-reducibility).

Both methods are randomized and approximate. What I would like to understand is this: If the decision problems to be solved in the hashing-based approach and the almost uniform sampling required in the JVV approach are of equivalent complexity, is there any algorithmic reason to prefer one method over the other?

To try and quantify the question, imagine that, for a given #P problem with an associated decision problem in NP, we have access to both (a) the NP oracle required for hashing-based counting, and (b) the almost uniform generator (not necessarily polynomial-time) required by JVV. Furthermore, suppose that each call to either the oracle or the generator incurs the same unit cost. If all I care about is the number of calls, which of the two approaches would I be better off using?

[1] Valiant, L. G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theor. Comput. Sci. 47, 85-95 (1986). ZBL0621.68030.

[2] Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V., Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci. 43, 169-188 (1986). ZBL0597.68056.

$\endgroup$

1 Answer 1

2
$\begingroup$

Note that in case of hashing-based, it is possible to make only O(log n) NP oracle calls where n is the number of variables of the Boolean formula while JVV-based reduction would make O(n) calls to approximate uniform generator.

When it comes to building a really practical counter, hashing-based approach is significantly better. (We have been building such a counter for the past decade: https://github.com/meelgroup/approxmc)

$\endgroup$

Your Answer

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

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