<p>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.</p>
<p>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: <a href="https://github.com/meelgroup/approxmc" rel="nofollow noreferrer">https://github.com/meelgroup/approxmc</a>)</p>

CC BY-SA 4.0
2022-12-27T07:42:37.930Z
2022-12-27T07:42:37.930Z
Kuldeep Meel
<p>Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:</p>
<blockquote>
<p>For any <span class="math-container">$\varepsilon &gt; 0$</span> there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula <span class="math-container">$f$</span> outputs a number <span class="math-container">$k$</span> such that <span class="math-container">$(1 -\varepsilon) \cdot \#f \leq k \leq (1 + \varepsilon) \cdot \# f$</span> with probability at least <span class="math-container">$1 - \varepsilon$</span>.</p>
</blockquote>
<p>I've seen this method referred to as hashing-based counting.</p>
<p>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).</p>
<p>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?</p>
<p>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?</p>
<p>[1] <em>Valiant, L. G.; Vazirani, V. V.</em>, <a href="http://dx.doi.org/10.1016/0304-3975(86)90135-0" rel="nofollow noreferrer"><strong>NP is as easy as detecting unique solutions</strong></a>, Theor. Comput. Sci. 47, 85-95 (1986). <a href="https://zbmath.org/?q=an:0621.68030" rel="nofollow noreferrer">ZBL0621.68030</a>.</p>
<p>[2] <em>Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V.</em>, <a href="http://dx.doi.org/10.1016/0304-3975(86)90174-X" rel="nofollow noreferrer"><strong>Random generation of combinatorial structures from a uniform distribution</strong></a>, Theor. Comput. Sci. 43, 169-188 (1986). <a href="https://zbmath.org/?q=an:0597.68056" rel="nofollow noreferrer">ZBL0597.68056</a>.</p>

<approximation-algorithms><counting-complexity><randomized-algorithms><approximation-hardness>
Hashing-based vs almost uniform sampling-based approximate counting
delete000
# Hashing-based vs almost uniform sampling-based approximate counting

(Asked by: username_0 on 2021-12-23)

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**](http://dx.doi.org/10.1016/0304-3975(86)90135-0), Theor. Comput. Sci. 47, 85-95 (1986). [ZBL0621.68030](https://zbmath.org/?q=an:0621.68030).

[2] *Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V.*, [**Random generation of combinatorial structures from a uniform distribution**](http://dx.doi.org/10.1016/0304-3975(86)90174-X), Theor. Comput. Sci. 43, 169-188 (1986). [ZBL0597.68056](https://zbmath.org/?q=an:0597.68056).

**Tags:** approximation-algorithms, counting-complexity, randomized-algorithms, approximation-hardness


---

## 1 answers

### Answer by username_1 on 2022-12-27. Score: 2

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


---

