Are there analogous works to PPSZ algorithm for #P? - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-20T11:47:37Z https://cstheory.stackexchange.com/feeds/question/48433 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/48433 8 Are there analogous works to PPSZ algorithm for #P? SagarM https://cstheory.stackexchange.com/users/52564 2021-02-19T11:16:31Z 2021-02-20T18:34:42Z <p>The PPSZ algorithm tells us that we can do SAT-solving for <span class="math-container">$k-$</span>CNF in time at-most <span class="math-container">$2^{1-(1-o(1))\frac{\pi^2}{6k}}$</span>.</p> <p>My question is that do we know such results for counting problems in class #P too ? For example, for #SAT do we know any algorithm that provably runs better than <span class="math-container">$O(2^n)$</span> ?</p> https://cstheory.stackexchange.com/questions/48433/-/48436#48436 7 Answer by Ryan Williams for Are there analogous works to PPSZ algorithm for #P? Ryan Williams https://cstheory.stackexchange.com/users/225 2021-02-19T14:31:01Z 2021-02-19T14:31:01Z <p>There are several #k-SAT algorithms in the literature which can beat <span class="math-container">$2^n$</span>. Here is a randomized one that gets <span class="math-container">$2^{n(1-1/O(k))}$</span> time (like PPSZ):</p> <p><a href="https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf" rel="noreferrer">https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf</a></p> <p>There is also a deterministic algorithm with <span class="math-container">$2^{n(1-1/O(k))}$</span> runtime behavior. Here is a link:</p> <p><a href="http://tmc.web.engr.illinois.edu/detapsp_soda.pdf" rel="noreferrer">http://tmc.web.engr.illinois.edu/detapsp_soda.pdf</a></p> <p>A caveat: this second algorithm uses exponential space. I believe it is open to find a deterministic algorithm with a similar running time and polynomial space. Be sure look on Google scholar for related references too.</p> https://cstheory.stackexchange.com/questions/48433/-/48448#48448 -2 Answer by Giorgio Camerani for Are there analogous works to PPSZ algorithm for #P? Giorgio Camerani https://cstheory.stackexchange.com/users/947 2021-02-20T18:34:42Z 2021-02-20T18:34:42Z <p>Recently, I have presented a randomized algorithm for #<span class="math-container">$k$</span>-SAT which counts the exact number of satisfying assignments in <span class="math-container">$2^{o(n)}$</span> time (and linear space), thereby refuting #ETH and related hypotheses:</p> <p><a href="https://arxiv.org/abs/2102.02624" rel="nofollow noreferrer">The #ETH is False, #k-SAT is in Sub-Exponential Time</a></p> <p>The crucial insight is: <strong>count without search</strong>. The algorithm counts all satisfying assignments without even trying to search for any single one of them. Thanks to the inclusion-exclusion principle, it is possible to count satisfying assignments by totally ignoring them and by visiting a completely different search space: that of monotone (unate) sub-formulae. A further insight allows, for random instances, to prune such search space so massively that only the last <span class="math-container">$n$</span> clauses do matter for the running time (regardless of the density <span class="math-container">$\Delta = \frac{m}{n}$</span> which in general might depend on <span class="math-container">$k$</span> exponentially), resulting into a <span class="math-container">$2^{\Theta(\frac{\log k}{k})n}$</span> time deterministic algorithm. A final simple trick allows to take any generic instance and inflate (i.e. dilute) it by randomly enlonging all its clauses and arranging them so that it looks random and fools the algorithm for random instances.</p> <p>The final running time for generic #<span class="math-container">$k$</span>-SAT instances is <span class="math-container">$2^{O\left(\frac{\log \log \log n}{\log \log n}n\right)}$</span>.</p>