4
$\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$

Your Answer

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

Browse other questions tagged or ask your own question.