8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

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.

$\endgroup$
-2
$\begingroup$

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

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)}$.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ – Huck Bennett Feb 21 at 6:20
  • $\begingroup$ 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). $\endgroup$ – Huck Bennett Feb 21 at 6:20
  • $\begingroup$ (I realize that Stack Exchange isn't the best place for these discussions -- feel free to email me if you want to respond elsewhere.) $\endgroup$ – Huck Bennett Feb 21 at 6:21
  • 2
    $\begingroup$ 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: link.springer.com/chapter/10.1007/978-3-642-21581-0_30. $\endgroup$ – Huck Bennett Feb 21 at 6:26
  • $\begingroup$ Hi Huck, I'm going to send you an email. $\endgroup$ – Giorgio Camerani Feb 21 at 14:15

Your Answer

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

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