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

CC BY-SA 4.0
2021-02-19T14:31:01.390Z
2021-02-19T14:31:01.390Z
Ryan Williams
<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>

CC BY-SA 4.0
2021-02-21T06:20:53.090Z
Hi Giorgio, I looked at your work and find it interesting. There are a couple of things I don't understand. 

1. The beginning of the proof of Theorem 2.4 is hard for me to follow, especially the part justifying Equation 2.8.
Huck Bennett
CC BY-SA 4.0
2021-02-21T06:20:56.597Z
2. In the proof of Lemma 2.3, you argue that after hitting critical saturation you'll be able to prune a subtree T_Psi all but a ~1/n^sigma fraction of the time, which is 1/poly(n) since you say that sigma is a constant in the proof of Theorem 2.4. So, for a single clause you can prune T_Psi w.h.p., but you will in general enumerate almost exponentially many Psi (even assuming for now that the bound on the number of such Psi from Equations 2.8 and 2.9 is okay).
Huck Bennett
CC BY-SA 4.0
2021-02-21T06:21:50.097Z
(I realize that Stack Exchange isn't the best place for these discussions -- feel free to email me if you want to respond elsewhere.)
Huck Bennett
CC BY-SA 4.0
2021-02-21T06:26:11.423Z
By the way, some work I did a long time ago discusses essentially the same pruning heuristic for solving #SAT via inclusion-exclusion but without any provable runtime gain: https://link.springer.com/chapter/10.1007/978-3-642-21581-0_30.
Huck Bennett
CC BY-SA 4.0
2021-02-21T14:15:12.377Z
Hi Huck, I'm going to send you an email.
Giorgio Camerani
CC BY-SA 4.0
2021-02-25T18:17:40.917Z
I would suggest to add the detailed answer to your answer for the community to see them. You are making an "extraordinary claim", and skeptism of the TCS community is expected and healthy. It would be nice to give the community the opportunity to react to your claims and ask clarifications on the subtleties of this proof. Right now, most people will expect that there is likely a subtle mistake somewhere, and this looks like a natural reaction (I did not downvote, but I would'nt believe the result until it gets accepted at a strong peer reviewed venue and experts indicate it seems to work).
Geoffroy Couteau
CC BY-SA 4.0
2021-02-20T18:34:42.503Z
2021-02-20T18:34:42.503Z
Giorgio Camerani
<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>

<sat><counting-complexity>
Are there analogous works to PPSZ algorithm for #P?
SagarM
# Are there analogous works to PPSZ algorithm for #P?

(Asked by: username_0 on 2021-02-19)

The PPSZ algorithm tells us that we can do SAT-solving for
$k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$.

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 $O(2^n)$ ?

**Tags:** sat, counting-complexity


---

## 2 answers

### Answer by username_1 on 2021-02-19. Score: 7

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets
$2^{n(1-1/O(k))}$ time (like PPSZ):

[https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi\_2012\_soda.pdf](https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf)

There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link:

<http://tmc.web.engr.illinois.edu/detapsp_soda.pdf>

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.


---

### Answer by username_2 on 2021-02-20. Score: -2

Recently, I have presented a randomized algorithm for #$k$-SAT which counts the exact number of satisfying assignments in $2^{o(n)}$ time (and linear space), thereby refuting #ETH and related hypotheses:

[The #ETH is False, #k-SAT is in Sub-Exponential Time](https://arxiv.org/abs/2102.02624)

The crucial insight is: **count without search**. 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 $n$ clauses do matter for the running time (regardless of the density $\Delta = \frac{m}{n}$ which in general might depend on $k$ exponentially), resulting into a $2^{\Theta(\frac{\log k}{k})n}$ 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.

The final running time for generic #$k$-SAT instances is $2^{O\left(\frac{\log \log \log n}{\log \log n}n\right)}$.

> **Comments:**
> **username_3**: Hi Giorgio, I looked at your work and find it interesting. There are a couple of things I don't understand.   1. The beginning of the proof of Theorem 2.4 is hard for me to follow, especially the part justifying Equation 2.8.  
> **username_3**: 2. In the proof of Lemma 2.3, you argue that after hitting critical saturation you'll be able to prune a subtree T_Psi all but a ~1/n^sigma fraction of the time, which is 1/poly(n) since you say that sigma is a constant in the proof of Theorem 2.4. So, for a single clause you can prune T_Psi w.h.p., but you will in general enumerate almost exponentially many Psi (even assuming for now that the bound on the number of such Psi from Equations 2.8 and 2.9 is okay).  
> **username_3**: (I realize that Stack Exchange isn't the best place for these discussions -- feel free to email me if you want to respond elsewhere.)  
> **username_3**: By the way, some work I did a long time ago discusses essentially the same pruning heuristic for solving #SAT via inclusion-exclusion but without any provable runtime gain: https://link.springer.com/chapter/10.1007/978-3-642-21581-0_30.  
> **username_2**: Hi Huck, I'm going to send you an email.  
> **username_4**: I would suggest to add the detailed answer to your answer for the community to see them. You are making an "extraordinary claim", and skeptism of the TCS community is expected and healthy. It would be nice to give the community the opportunity to react to your claims and ask clarifications on the subtleties of this proof. Right now, most people will expect that there is likely a subtle mistake somewhere, and this looks like a natural reaction (I did not downvote, but I would'nt believe the result until it gets accepted at a strong peer reviewed venue and experts indicate it seems to work).  

---

